[알고리즘] 25. 모든쌍의 최단경로
all pair 는 single-source 를 |V|만큼 돌릴때 나올수 있는데 이것보다 더 나은 방식으로 구할꺼임
여기서 adjacent matrix 를 이용해 표현 할꺼임
wij = i=j : 0
i != j 이고 실제 있는 간선 : 그 weight
다르면서 실제 없는 간선 :무한대
Dynamic programming algorithm :
1. optimal solution 구조를 정의해라
2. 그 solution을 재귀적으로 정의 해라
3. bottom up 방식으로 해를 구해라
4. optimal solution 을 도출해라
structure of shortest path
shortest path의 하위 부분은 전부 shortest path이다.
-> wij 에서 i=j 이면 w 가 0/ i!=j 이면 k 를 지나간다는 가정하에 두 경로를 합친다
recursive solution to all pairs shortest paths problems
computing the shortest path weights bottom up
Extend-Shortest-Path(L,W)
n = L.rows
let L' = (l'ij) be a new nxm matrix
for i =1 to n
for j =1 to n
l'ij =무한
for k =1 to n
l'ij = min(l'ij, lik+wkj)
Slow-All-Pairs-Shortest-Paths(W)
n = W.rows
L(1) = W
for m =2 to n-1
let L(m) new nXn matrix
L(m) = Extend-Shortest-Path(L(m-1), W)
return L(n-1)
O(n^4)
Author And Source
이 문제에 관하여([알고리즘] 25. 모든쌍의 최단경로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rkdud007/알고리즘-25.-모든쌍의-최단경로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)