Floyd

- 최단 경로 알고리즘

- 모든 정점 사이의 최단 경로를 구하려면 다익스트라의 알고리즘을 정점의 수만큼 반복 실행, But 모든 정점 사이의 최단 거리를 구하려면 더 간단한 알고리즘으로 플로이드 알고리즘

- 2차원 배열을 이용하여 3중 반복을 하는 루프로 구성

- distance 배열없이 그래프를 갱신함.

- 다익스트라로 모든 정점의 쌍으로 최단 경로를 구하려면 알고리즘 n번 반복, 전체 복잡도는 


- 시간복잡도: 

'Algorithm' 카테고리의 다른 글

알고리즘 - 순차 탐색  (1) 2015.11.14
알고리즘 - 위상 정렬  (0) 2015.11.14
알고리즘 - 플로이드  (0) 2015.11.14
알고리즘 - 다익스트라  (0) 2015.11.14
알고리즘 - 프림  (0) 2015.11.13
알고리즘 - 크루스칼  (0) 2015.11.13

+ Recent posts