hyun9iOS

플로이드 워셜(Floyd-Warshall)은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 에 사용할 수 있는 알고리즘이다. 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다익스트라와 다른 점이다. 노드의 개수가 n 개일때 n 번의 단계를 수행하며 단계마다 O(N²) 의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다. 그래서 총 시간 복잡도는 O(N³)이다. 즉, 모든 지점을 시작으로 삼고 모든 지점에 대해서 끝으로 삼아서 최단 거리를 구하는데 모든 노드를 경유지로 삼는 과정인 n 번의 단계를 수행 한다. min(시작 → 끝, 시작 → 경유 + 경유 → 끝) 를 구하는 것이다. 다익스트라 알고리즘은 출발 노드가 1개이므로 다른 모든 노..