ALGORITHM/최단경로

Floyd-Warshall Algorithm (최단경로)

이 알고리즘은 플로이드 알고리즘, 로이-워셜 알고리즘, 로이-플로이드 알고리즘, 또는 WFI 알고리즘으로 알려져 있다. 알고리즘 Floyd-Warshall 알고리즘은 그래프에서 지날 수 있는 모든 경로를 비교한다. 시간 복잡도는 O(n^3)으로, 코드로 짜면 3중의 중첩 반복문을 가진다. 노드i에서 노드j까지 가는 방법은 2가지 중 하나일 것이다. (중간에 k란 노드가 있다고 하자) i에서 바로 j로 가는 경우 i에서 k를 거쳐 j로 가는 경우 위 2가지의 경우의 수 중에서 최단경로가 결국 우리가 구하고자 하는 값이 된다. 따라서 아래와 같이 나타낼 수 있다. floyd(i,j,k) = min(i에서 j로 가는 최단거리, i에서 k로 가는 최단거리 + k에서 j로 가는 최단거리) 코드로 나타내면 아래와같..