다 대 다 최단 거리를 구한다면

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) ⇒ 엣지가 있으면 그 웨이트. 없으면 무한