[C++]플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)

2020-02-27 228 words 2 minutes

Contents

플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)

한번의 실행으로 “모든 노드” 간 최단 경로를 구하는 알고리즘.

시간복잡도

$$ O(n^3) $$

위 그림의 초기값은 다음과 같다.

0	5	∞	9	1
5	0	2	∞	∞
∞	2	0	7	∞
9	∞	7	0	2
1	∞	∞	2	0

이때,

1 번 노드를 중간 노드로 한다면,

2 - 1 - 4 로 가는 길이 14 짜리 경로를 만들 수 있고,

2 - 1 - 5 로 가는 길이 6 짜리 경로를 만들 수 있다.

0	5	∞	9	1
5	0	2	`14`	`6`
∞	2	0	7	∞
9	`14`	7	0	2
1	`6`	∞	2	0

위와 같은 방식으로 모든 노드가 중간노드로 선택될 때까지 반복한다.

이때 반복이 종료된다면, 모든 노드간 최단거리가 들어있게 된다.

0	5	7	3	1
5	0	2	8	6
7	2	0	7	8
3	8	7	0	2
1	6	8	2	0

코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


for (int i = 1; i <= n; i++) 
	for (int t = 1; t <= n; t++)
		if(i == t)	d[i][t] = 0;
		else if(a[i][t])	d[i][t] = a[i][t];
		else	d[i][t] = INF;

for (int i = 1; i <= n; i++) 
	for (int t = 1; t <= n; t++)
		for (int y = 1; y <= n; y++)
            d[t][y] = min(d[t][y], d[t][i] + d[i][y]);