플로이드 알고리즘 (Floyd-Warshall algorithm)

(출처: 종만북)

모든 쌍 간의 최단거리를 구할 때 간단하게 구현할 수 있는 알고리즘은 플로이드 알고리즘(Floyd-Warshall algorithm, 플로이드-와샬 알고리즘)이 있습니다.

시간복잡도는 O(V^3)입니다.

 

경로가 거쳐가는 정점들을 경유점이라고 정의합시다. 그러면 정점 집합 S에 포함된 정점만을 경유점으로 사용해 u에서 v로 가는 최단 경로의 길이를 \(D_S (u, v)\)라고 표기합시다.

S에 포함된 정점만을 경유점으로 사용해 u에서 v로 가는 최단 경로를 알고 있다고 할 때 S 중에 정점을 하나 골라 x라고 하면 최단경로는 x를 경유할 수도, 경유하지 않을 수도 있습니다.

따라서 \(D_S (u,v)\)를 아래와 같이 재귀적으로 표현할 수 있습니다.

\[D_{S}(u,v)= min\left\{ \begin{matrix}
D_{S-\{x\}}(u,x)+D_{S-\{x\}}(x,v) \\
D_{S-\{x\}}(u,v)
\end{matrix}\right. ,x\in S\]

이 점화식을 동적계획법으로 풀고 최적화를 하면 아래와 같이 식이 나옵니다. (유도 과정은 나중에 작성)

int V;
const int INF = 987654321;
int adj[MAX_V][MAX_V];

void floyd() {
	for (int i = 0; i < V; ++i)
		for (int j = 0; j < V; ++j)
			if (i != j && !adj[i][j])
				adj[i][j] = INF;

	for (int k = 0; k < V; ++k)
		for (int i = 0; i < V; ++i)
			for (int j = 0; j < V; ++j)
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}