[알고리즘] 플로이드 와샬 ( Floyd-warshall )

플로이드 와샬

플로이드 와샬은 최단경로를 DP(Dynamic Programming)형태의 문제로 정의하고 풀어낸다.

 

모든 정점 쌍의 경로에 대해 기존 경로(i -> … -> j)가 최단 경로 인지,

어느 한 정점을 경유해서 가는 경로(i -> … -> k -> …  -> j)가 최단 경로인지 비교한다.

 

이것을 경유지를 1 ~ N번 정점으로 놓고 계산한다.

계산이 완료되면 어느 한 경로가 어디를 경유하든 최단거리임이 만족된다.

이 알고리즘이 왜 DP인가?

-> 쉽게 설명하면 [기존 경로] VS [다른 기존 경로]의 재조합이다.

    기존 경로를 사용해서 새로운 경로를 만들기 때문에 DP이다.

ShortestPath(i, j, k)

shortestPath(i, j, k)라는 문제는

i번 정점에서 j번 정점까지, 1~k번 정점만 사용할 때의 최단 거리를 구하라는 의미이다.

k단계 문제를 풀려면 k-1단계의 정보가 필요하다. 그래서 k=1~N까지 시도하며 정보를 계속해서 갱신하게 된다.

이때, k-1단계 이전의 정보는 더 이상 필요하지 않아서 3차원 배열을 사용하지 않고 슬라이딩 윈도우 기법을 적용하여 덮어써서 2차원 배열 dis만 가지고도 해결이 된다.

 

식으로 나타내면 다음과 같다.

i에서 j로 가는 최단 거리

= min(경유 없이 바로 갈 때 거리, 1번 정점 경유할 때 거리, 2번 경유, ... , n번 경유)

 

dis[i][j] : i~j에 간선이 없으면 INF, 있으면 그 간선 가중치로 초기화

k를 경유할 수 있고 k를 경유하는 거리가 더 짧으면 dis[i][j]를 dis[i][k] + dis[k][j]로 갱신

for (int k = 1; k <= n; k++) { // 경유지
    for (int i = 1; i <= n; i++) { // 출발
        for (int j = 1; j <= n; j++) { //도착
            if (dis[i][k] && dis[k][j] && dis[i][j] > dis[i][k]+dis[k][j]) {
                dis[i][j] = dis[i][k] + dis[k][j];
            }
        }
    }
}

정리

플로이드 와샬 알고리즘은 

• 모든 (i, j)쌍에 대해서 최단거리를 구한다. (모든 출발점 ~ 모든 도착점에 대한 계산)
• 음수 가중치가 있는 그래프에서도 작동한다.
• 시간 복잡도는 O(N^3)이다.

따라서 코딩 테스트에서 모든 노드가 출발점이자 도착점이 될 수 있는 문제이고 시간 복잡도 O(N^3)안에 해결 가능한 입력이 주어진다면 플로이드와샬을 사용하자.