플로이드워셜

플로이드워셜 알고리즘은 모든 정점 쌍 사이의 최단거리를 다 구해낸다. 다익스트라는 O(V(E+VlogV)), 벨만 포드는 O(VVE)에 할 것을 프로이드 워셜은 O(V^3)만에 끝낼 수 있다.

플로이드워셜은 최단 경로를 DP형태의 문제로 정의하고 풀어낸다.

shortestPath(i, j, k)는 i에서 j로, 1~k번 정점만 사용할 때의 최단거리를 구하라는 것이다. k단계 문제를 풀려면
k-1단계의 정보가 필요한데, 그래서 k=1~N까지 시도하며 정보를 계속 갱신한다.
이것을 k번 반복하면 마지막엔 더이상 갱신되지 않는 최단경로 배열 dist가 완성되는 것이다.

(이번이 k단계, 1~k번 정점을 사용하여 도달 가능한 최단거리를 구하는 단계라면 지금까지 dist 배열에는 1~k-1번 정점만 사용하여 나올 수 있는 최단거리가 있다.)

즉, i와 j에 대해 k번 정점을 사용해 우회하면, 지금보다 짧아지는가? 이 질문을 모든 정점쌍에 던져보는 것이라고 이해하면 된다.
(dist[i][j] > dist[i][k] + dist[k][j])
플로이드워셜 문제는 코드의 간단함과 목적의 명확함 때문에, 어려운 문제들은 최단경로 문제인지 모르게 포장되어 나오기도 한다.