1. 정의 및 특징

  • 모든 정점 사이의 최단 거리
  • 다익스트라 N번 수행하는 것보다 빠름
  • 시간복잡도 : O(V^3) (단, V는 정점의 개수)
  • 정점쌍 (i, j)에 대해 정점 k 경유지를 거쳤을 때 더 빠른 경우 갱신한다.
  • dp[i][j] 는 정점 i에서 정점 j 까지의 거리
for (k = 0; k < V; k++)
	for (i = 0; i < V; i++)
		for (j = 0; j < V; j++)
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

2. 예제 코드



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40



#include <iostream>

#define MAX 105
#define INF 0x7fffffff

using namespace std;

int V, dp[MAX][MAX];

void floydWarwhall() {
	for (int k = 1; k <= V; k++) {
		for (int i = 1; i <= V; i++) {
			for (int j = 1; j <= V; j++) {
				if \(dp\[i]\[k] == INF \|| dp\[k]\[j] == INF)
					continue;

				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
}

int main() {
	cin >> V;

	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++) {
			cin >> d[i][j];
			if (d[i][j] == 0) d[i][j] = INF;
		}
	}

	floydWarwhall();

	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++) 
			cout << dp[i][j] << " ";
		cout << endl;
	}
}