플로이드 와샬
개념
모든 최단 경로를 구하는 알고리즘으로 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 다익스트라와 차이가 있다. 다익스트라와 다르게 음의 간선이 있어도 계산 가능하다.
임의의 정점 S에서 E까지 가는데 걸리는 최단 거리를 구하기 위해, S와 E 사이의 노드인 M에 대해 S에서 M까지 걸리는 최단 거리와 M에서 E까지 가는데 걸리는 최단 거리를 이용한다.
구현
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
41
42
43
44
45
//Floyd calculates shortest dist from all nodes to all nodes
/*
0. Initialize d with inf except adj nodes
1. Find d[s][e] by comparing current d[s][e] with d[s][m]+d[m][e]
*/
#include <stdio.h>
#define INF 1<<20
int d[1000][1000];
int n, m;
void Init()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if(i!=j) d[i][j] = INF;
}
void Floyd()
{
for (int m = 1; m <= n; m++) //가운데 노드
for (int s = 1; s <= n; s++) //시작 노드
for (int e = 1; e <= n; e++) //마지막 노드
if (d[s][e] > d[s][m] + d[m][e])
d[s][e] = d[s][m] + d[m][e]; //가운데를 거쳐가는 것이 더 빠르면 그걸로 업데이트한다.
}
int main()
{
scanf("%d %d", &n, &m); //n: 노드의 개수, m: 간선의 개수
Init(); //d의 모든 값을 무한으로 초기화(단, d[i][i]는 0)
for (int i = 0; i < m; i++) { //인접행렬 입력받기
int x, y, c;
scanf("%d %d %d", &x, &y, &c);
d[x][y] = c;
}
Floyd();
for (int i = 1; i <= n; i++) //모든 경로의 최단거리 출력
for(int j=1; j<=n; j++)
printf("Shortest dist from %d to %d: %d\n", i, j, d[i][j]);
}
참고: https://namu.wiki/w/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98