플로이드-워셜 알고리즘 (Floyd-Warshall)

• 플로이드-워셜 알고리즘

 다익스트라가 하나의 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이라면 플로이드-워셜 알고리즘은 모든 노드 간의 최단 경로를 구하는 알고리즘이다. 그리고 다익스트라와 다르게 음의 간선도 사용이 가능하다.

 

 플로이드-워셜이 어떤 알고리즘인지 간단하게 보자.  노드가 a ~ e까지 5개가 있다 하고 노드를 연결하는 간선의 가중치가 각각 다르다고 하자. 만약 a -> b의 가중치가 k라 할때 플로이드-워셜 알고리즘은 a에서 b로가는 경로의 최솟값을 찾기 위해 a -> (경유지) -> b의 경우의 가중치를 k와 비교하여 최솟값을 구한다. 예를들면 여기서는 경유지에 a ~ e까지 5개를 넣어서 비교하는데 (경유지가 a 또는 b인 경우는 a -> b와 같음) 만약 a -> d -> b의 가중치가 k - 3이라면 a -> b의 가중치가 k에서 k - 3이 되는 것이다.

  이런식으로 모든 노드간의 거리 중간에 경유지를 하나씩 넣어 원래 가중치와 경유지가 있는 루트의 가중치를 비교하여 최솟값을 구하면 모든 최단경로를 구할 수 있다는 것이 플로이드-워셜 알고리즘이다. 

 

 Java로 이를 구현하는 방법은 우선 2차원 배열을 만들어서 노드 i에서 노드 j로 가는 가중치를 저장해 놓는다. 이때 초기화를 i == j일때는 값을 0으로 그렇지 않을 때에는 INF (=1000000000)로 해준다. 그리고 문제에서 입력받은 간선간의 가중치를 배열에 입력하고 다음과 같이 3중 for문을 돌린다.

for (int i = 1; i < n + 1; i++)
    for (int j = 1; j < n + 1; j++)
        for (int k = 1; k < n + 1; k++)
            time[j][k] = Math.min(time[j][k], time[j][i] + time[i][k]);

여기서 time이라는 2차원배열이 가중치의 값들이 적혀져있는 배열이고 i는 경유지 j는 출발지 k는 도착지를 의미한다.

따라서 경유지가 1일때 j -> k 와 j -> i -> k 의 값을 비교해 최솟값을 time[j][k]에 넣고 이 과정을 반복해 경유지가 1일때의 경우를 전부 찾아봤으면 경유지가 2일때를 다시 반복하고 이를 경유지가 n일때까지 반복하여 각 노드간의 최단 경로를 구할 수 있다. 이 경우 3중 for문을 돌리기 때문에 시간복잡도는 O(N^3)가 된다. 

 

---

reference

 - https://chanhuiseok.github.io/posts/algo-50/