- Floyd
- 최단 경로 알고리즘
- 모든 정점 사이의 최단 경로를 구하려면 다익스트라의 알고리즘을 정점의 수만큼 반복 실행, But 모든 정점 사이의 최단 거리를 구하려면 더 간단한 알고리즘으로 플로이드 알고리즘
- 2차원 배열을 이용하여 3중 반복을 하는 루프로 구성
- distance 배열없이 그래프를 갱신함.
- 다익스트라로 모든 정점의 쌍으로 최단 경로를 구하려면 알고리즘 n번 반복, 전체 복잡도는
- 시간복잡도:
'Algorithm' 카테고리의 다른 글
| 알고리즘 - 순차 탐색 (1) | 2015.11.14 |
|---|---|
| 알고리즘 - 위상 정렬 (0) | 2015.11.14 |
| 알고리즘 - 다익스트라 (0) | 2015.11.14 |
| 알고리즘 - 프림 (0) | 2015.11.13 |
| 알고리즘 - 크루스칼 (0) | 2015.11.13 |