[알고리즘] 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)