1. 용도
Graph에서 All pairs Shortest Path 구하기 == 그래프 내의 모든 노드쌍에 대한 최단거리 구하기.
| Input | Directed-weighted Graph |
| Output | All pairs Shortest Path (ex. Adjacency Matrix) |
2. IDEA
점화식으로 부터 이 알고리즘이
'Dynamic Programming' 류의 알고리즘임을 알 수 있다.
3. Pseudo Code
4. Time Complexity
Pseudo Code에서 알 수 있듯이
최초의 Adjacency Matrix를 형성하는 2중 for Loop은 O(n^2)
Shortest Path를 갱신하는 3중 for Loop 은 O(n^3)
∴ O(n^3)
참고 자료
플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서, 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다.[1][2] 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다. 이 알고리즘의 일부 버전은 관계 R
ko.wikipedia.org
'Algorithm > Algorithm (이론)' 카테고리의 다른 글
| Backtracking (0) | 2021.01.26 |
|---|---|
| [Data Structure] Hash (0) | 2020.10.17 |
| Strongly Connected Component (0) | 2019.11.23 |
| Topological Sort(위상 정렬) (0) | 2019.11.22 |
| 에라토스테네스의 체 (소수 구하기) (feat. 백준 1978, 1929) (0) | 2019.11.12 |