다 대 다 최단 거리를 구한다면
1 대 다인 다익스트라 를 n 번 하면 구할 수 있다 N * O( N^2 * log N) ⇒ O(N^3 * log N)
이 때 logN은 바이너리 힙에서 현재 가장 가까운 노드를 선택하는 pop (그리고 heapify ) 때문에
생기는 연산이다. 그리디한 과정
플로이드와 워셜은 위 그리디한 과정을 dp를 통해 log N 을 O(1) 로 줄여
총 O(N^3)으로 다 대 다 최단 거리를 구할 수 있게 고안했다.
sp = short path , d = distance
sp 사이의 최단경로에 k 가 포함된다면
sp(i,j) = sp(i, k) + sp(k,j)
d(i, j) = d(i,k) + d(k, j)
그렇다면 어떤 노드를 k로 정하는가
⇒ 이왕이면 경로 사이에 있는 노드 중에 번호가 제일 큰것으로 고르자
예) 3번 노드에서 8번 노드 3 → 1 → 9 → 4 → 6 → 8 이면,
k를 9로 하자. sp(3, 8) = sp(3,9) + sp(9,8)
sp_k(i, j) = sp_k-1(i,k) + sp_k-1(k,j)
sp_k는 i 와 j 사이의 노드 는 k 이하라는 것을 의미
d에 관해서 생각한다면
d 테이블이 생길 것이다
d_0(i,j) ⇒ 엣지가 있으면 그 웨이트. 없으면 무한