최단 경로 탐색
-
[알고리즘/플로이드] 플로이드-와샬(Floyd-Warshall) 알고리즘Mhwan's Study/Algorithms 2021. 2. 12. 03:49
플로이드 와샬 알고리즘은 다익스트라, 벨만포드 알고리즘과는 달리 모든 정점간의 최단거리를 구하는 알고리즘입니다. 이 알고리즘은 동적 프로그래밍 기법을 사용한 알고리즘으로 O(V^3)이라는 시간복잡도가 필요하며, 다익스트라 알고리즘을 모든 정점 V만큼 반복한 것보다 더 빠릅니다. 또한 음의 가중치 간선은 존재할 수 있으나 음의 가중치 사이클은 없다고 가정합니다. # 경유점 경유점이라는 개념은 플로이드 와샬 알고리즘의 핵심입니다. 어떤 경로든 최단 경로사이의 경유지가 존재할 것입니다. 위 그래프를 가정하면 1->2를 가는 최단 경로는 (1->3->4->2)가 되고, 3, 4는 1->2사이의 경로에 존재하는 경유점이 됩니다. 즉, u->v로 가는 최단 경로가 있다면 이것은 크게 두가지로 나뉠겁니다. 1. 경로..