📚 목차
요약
1. 플로이드 워셜 (Floyd-warshall)
1. 플로이드 워셜
- 그래프에서 최단 거리를 구하는 알고리즘
- 시간 복잡도는 O(V^3)으로 빠르지 않은 편이다.
2. 플로이드-워셜 핵심 이론
- 노드 A에서 노드 B까지는 경로 road가 있고 경로 road에 노드 K가 포함되어 있다고 하자
- 그럴 때, 노드 A에서 노드 K까지, 노드 K에서 노드 B까지의 최단 경로는 경로 road의 일부분이라는 것!
3. 플로이드 워셜 예시
- 그래프를 나타내는 최단 거리 배열 D를 만든다.
최단 거리 배열 D
| S/E |
1 |
2 |
3 |
4 |
5 |
| 1 |
0 |
8 |
3 |
∞ |
∞ |
| 2 |
∞ |
0 |
∞ |
-4 |
15 |
| 3 |
∞ |
∞ |
0 |
13 |
∞ |
| 4 |
∞ |
∞ |
∞ |
0 |
2 |
| 5 |
∞ |
∞ |
∞ |
5 |
0 |
- 배열에서 각 요소가 나타내는 것은 노드 S에서 노드 E까지의 최단 거리를 나타낸다.