Floyd Algorithm

* 배열의 인덱스가 1부터 시작한다고 가정합니다.

([1] = 1번째 와 같이 이해하기 쉽도록)

 

- 알고리즘 정의

각 vertex에서 다른 모든 vertices의 최단 경로를 구하는 알고리즘. (mulit source-multi destination)

비슷한 역할을 수행하는 알고리즘에는 다익스트라 알고리즘이 있다. (single source-multi destination)

 

이 알고리즘을 이해하기 위해 몇가지 규칙을 만들자.

• D(k)[i][j]: vertex i 에서 vertex j로 가는 최단 경로를 저장.
                   단, 최단 경로를 생성하는 vertex는 {v1, v2, ..., vk}에서만 사용할 것.
• D(0)[i][j]: vertex i 에서 vertex j로 가는 최단 경로지만, 경유하는 vertex가 없음.
                   즉, vertex i와 vertex j 사이의 거리 W[i][j]를 의미.

 

예로 들어 위 그림에서 D(3)[2][5]가 의미하는 바는, {v1, v2, v3}을 경유해서

v2 -> v5로 가는 최단 경로를 뜻한다.

이 때, v3을 경유하면서 v2 -> v5로 가는 경로가 없다. 따라서 D(2)[2][5]와 값이 같아진다.

위 값은 14가 될 것이다.

 

이제 D(k)[i][j]와 D(k-1)[i][j] 사이의 관계를 살펴보자.

Case 1. vk가 최단 경로를 만드는데 도움이 안되는 경우

vi -> vj로 가는 모든 최단 경로에서 vk를 지나지 않는 경우이다.

위 경우에는 D(k)[i][j]와 D(k-1)[i][j]의 값이 같을 것이다.

따라서 다음과 같은 관계가 성립된다.

D(k)[i][j] = D(k-1)[i][j]

 

Case 2. vk가 최단 경로를 만드는데 도움이 되는 경우

vi -> vj로 가는 모든 최단 경로에서 vk를 지나는 경우이다.

위 경우에는 vi -> vk로 가는 최단 경로 + vk -> vj로 가는 최단 경로가 최단 경로가 될 것이다.

따라서 다음과 같은 관계가 성립된다.

D(k)[i][j] = D(k-1)[i][k] + D(k-1)[k][j]

 

vk를 일부 최단 경로만이 지나는 경우는 고려하지 않아도 된다.

왜냐하면 Principle of Optimality (최적성의 원칙)에 따라 D(k-1)[i][j]에 이미 고려가 되어 있기 때문이다.

(최적의 해는 최적의 부분해들의 합으로 이루어 진다는 원칙)

 

Case 1, 2를 합치면 D(k)[i][j]와 D(k-1)[i][j]의 관계를 얻을 수 있다.

D(k)[i][j] = min(D(k-1)[i][j], D(k-1)[i][k] + D(k-1)[k][j])

 

- Pseudocode

public static void floyd (int n, number[][] W,
                          number[][] D, number[][] P) {
    index k, i, j;
    for (i=1; i<=n; i++)
        for (j=1, j<=n; j++)
            P[i][j] = 0;
    
    D = W;
    for (k=1; k<=n; k++)
        for (i=1; i<=n; i++)
            for (j=1; j<=n; j++)
                if (D[i][j] > D[i][k] + D[k][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                    P[i][j] = k;
                }
}

// Print path
public static void floydPath (index i, index j) {
    if (P[i][j] == 0) return;
    
    floydPath(i, P[i][j]);
    system.out.print(" v" + P[i][j]);
    floydPath(P[i][j], j);
}

D(k)[i][j]를 위해 3차원 배열을 사용해야 할 필요는 없다.

궁극적인 목표는 D(n)[i][j]를 구하는 것이기 때문에 2차원 배열을 사용하여

k값을 1부터 n까지 업데이트 해가는 방식을 사용하면 된다.

 

W배열에는 edge에 대한 weight값이 들어있고,

D배열에는 최단 경로에 대한 데이터를 저장 및 업데이트,

P배열에는 최단 경로에 해당하는 vertex를 저장한다.

 

bottom-up 방식을 사용하기 때문에 초기값으로 D배열을 초기화 해야 하는데,

가장 bottom인 D(0)[i][j], 즉, W[i][j]로 초기화 한다.

이후 k 값을 1~n까지 증가시키며 i, j 루프를 돌아 D값을 업데이트 한다.

D가 업데이트 된다는 뜻은 vertex k를 지날 때 최단 경로가 된다는 뜻이므로,

P[i][j]에 k 값을 업데이트 하여 최단 경로가 되는 vertex를 업데이트 한다.

 

최단 경로 출력은 P 배열을 재귀 호출하여 구하게 된다.

vi -> vj 최단 경로는 k를 경유했을 것이고,
이는 vi -> ... -> vk -> ... -> vj 가 최단 경로라는 뜻이다.

그리고, vi -> vk, vk -> vj 최단 경로는 m, n를 경유했을 것이고,
이는 vi -> ... -> vm -> ... -> vk -> ... -> vn -> ... -> vj 가 최단 경로라는 뜻이다.

...(재귀 호출)

 

- Time complexity

Basic Operation: an assignment of D[i][j]

Input Size: n, number of vertices

 

* Every case: T(n) = n^3 [Θ(n^3)]