플로이드-와샬(Floyd-Warshall) 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 특히 음의 가중치가 포함된 그래프에서도 동작하지만, 음의 사이클(negative cycle)이 있으면 고장난다.
플로이드 와샬의 기본 개념
플로이드 와샬은 기본적으로 Dp(Dynamic Programming)알고리즘을 사용하는 알고리즘이다. 플로이드 와샬의 핵심은 "거쳐가는 경로"이다. 플로이드 알고리즘은 "dp[i][j][k] = "i에서 j사이 거쳐가는 모든 정점의 번호가 k 이하인 최단거리"를 기반으로 둔 것이다.
- 그래프 표현:
그래프는 일반적으로 n x n 크기의 인접 행렬로 표현된다. 여기서 n은 그래프의 정점의 수이다. 이 행렬의 각 요소 Floyd[i][j]는 정점 i에서 정점 j로 가는 경로의 가중치다. 만약 두 정점 사이에 경로가 없으면 무한대(∞)로 설정한다. - 최단 경로 갱신:
알고리즘은 세 개의 중첩 루프를 사용하여 최단 경로를 반복적으로 갱신한다. 각 단계에서 중간 정점 k를 경유하는 경로가 직접 연결된 경로보다 더 짧은 경우, 그 경로를 최단 경로로 업데이트한다.
플로이드 와샬 알고리즘의 시간 복잡도는 O(n³)이다.
플로이드 와샬의 동작 방법
위와 같은 그래프를 가 주어졌을 때 모든 노드에서의 최단경로를 구해보자.
우선 직접적으로 보이는 경로만 적어보자.
| 1 | 2 | 3 | 4 | |
| 1 | INF | 3 | 6 | INF |
| 2 | INF | INF | 1 | 7 |
| 3 | INF | INF | INF | 4 |
| 4 | INF | INF | INF | INF |
와 같이 채워진다. 이제 플로이드 와샬의 핵심인 "거쳐가는 경로"를 기준으로 배열을 갱신시켜가면된다.
-1을거쳐가는 경우 : 갱신가능한 구간이 없다.
-2를 거쳐가는 경우
| 1 | 2 | 3 | 4 | |
| 1 | INF | 3 | 4 | 10 |
| 2 | INF | INF | 1 | 7 |
| 3 | INF | INF | INF | 4 |
| 4 | INF | INF | INF | INF |
1 -> 2 -> 4로 가는 경우를 갱신
1 -> 2 -> 3로 가는 경우를 갱신
-3을 거쳐가는 경우
| 1 | 2 | 3 | 4 | |
| 1 | INF | 3 | 4 | 8 |
| 2 | INF | INF | 1 | 7 |
| 3 | INF | INF | INF | 4 |
| 4 | INF | INF | INF | INF |
1 -> 3 -> 4로 가는 경우를 갱신
-4를 거쳐가는 경우 : 갱신할 구간이 없다.
플로이드 와샬의 기본 문제를 풀어보자.
백준 플로이드(11404번) 문제를 살펴보자.
소스 코드
#include <stdio.h>
int n, m, w[110][110], d[110][110], cnt;
void fyd()
{
int i, j, k;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
d[i][j] = w[i][j];
if (d[i][j] == 0) d[i][j] = 987654321;
}
}
for (k = 1; k <= n; k++) {
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
}
int main()
{
int i, j;
int a, b, c;
scanf("%d %d", &n, &m);
for (i = 0; i <= n; i++) {
for (j = 0; j <= n; j++) {
w[i][j] = 987654321;
}
}
for (i = 1; i <= m; i++) {
scanf("%d %d %d", &a, &b, &c);
if(w[a][b] > c) w[a][b] = c;
}
fyd();
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (i == j) printf("0 ");
else if (d[i][j] == 987654321) printf("0 ");
else printf("%d ", d[i][j]);
}
printf("\n");
}
return 0;
}☆for문의 순서는 바뀌어선 안된다.