[C++] 플로이드 워셜 (Floyd Warshall) 알고리즘

플로이드 워셜 (Floyd Warshall) 알고리즘

두 점의 최단 거리를 구하기 위한 알고리즘

특히, 모든 정점 사이의 최단 거리를 구할 필요가 있을 때 사용하는 알고리즘이다. 그 이유는 알고리즘 수행 시 모든 정점 사이 최단 거리를 계산하며 사이에 있는 정점을 통해 최단 거리를 개선해 나가기 때문!

시간 복잡도

O(N^3)

 

과정

다음 그래프가 주어졌을 때, 플로이드 워셜 알고리즘을 수행하는 과정은 다음과 같다.

 

1. 먼저 모든 정점에서 다른 정점으로 (다른 점을 거치치 않고!) 바로 갈 수 있는 거리를 구한다.

	1	2	3	4	5
1	0	∞	1	∞	5
2	3	0	9	2	∞
3	4	4	0	∞	∞
4	∞	8	6	0	∞
5	∞	∞	∞	2	0

 

2. 그 후, 모든 정점에 대해 순회하며 해당 정점을 거쳤을 때의 거리가 더 짧아지는지를 살펴보고, 거리를 업데이트한다.

i에서 j로 갈 때, point를 거치게 된다면 총 거리는 distance[i][point] + distance[point][j]가 될 것이다.
이것을 distance[i][j]랑 비교해보면 된다.

위를 예시로 해당 작업을 수행해 보았다.

1을 거쳐서 가는 경우를 구한다

	1	2	3	4	5
1	0	∞	1	∞	5
2	3	0	9	2	8
3	4	4	0	∞	9
4	∞	8	6	0	∞
5	∞	∞	∞	2	0

 

2를 거쳐서 가는 경우를 구한다

	1	2	3	4	5
1	0	∞	1	∞	5
2	3	0	9	2	8
3	4	4	0	6	9
4	11	8	6	0	16
5	∞	∞	∞	2	0

 

3을 거쳐서 가는 경우를 구한다

	1	2	3	4	5
1	0	5	1	7	5
2	3	0	9	2	8
3	4	4	0	6	9
4	10	8	6	0	15
5	∞	∞	∞	2	0

 

4를 거쳐서 가는 경우를 구한다

	1	2	3	4	5
1	0	5	1	7	5
2	3	0	8	2	8
3	4	4	0	6	9
4	10	8	6	0	15
5	12	10	8	2	0

 

5를 거쳐서 가는 경우를 구한다

	1	2	3	4	5
1	0	5	1	7	5
2	3	0	8	2	8
3	4	4	0	6	9
4	10	8	6	0	15
5	12	10	8	2	0

 

3. 모든 정점에 대해서 순회가 끝나면 모든 정점 사이의 최단 거리를 알 수 있다.

	1	2	3	4	5
1	0	5	1	7	5
2	3	0	8	2	8
3	4	4	0	6	9
4	10	8	6	0	15
5	12	10	8	2	0

 

코드

Github Source

GitHub - yarncha/computer-science: Computer Science 공부 후 지식 쌓기