Floyd's Algorithm for shortest paths

1. Problem

- 여러 개의 노드가 연결되어 있는 그래프가 있다. 노드의 연결선에는 그 선을 지나는데 필요한 비용(가중치)이 있다. 모든 노드에 대해 다른 노드로 가는 데 필요한 가장 적은 비용(지름길)을 계산해보자.

 

2. Input

1) weighted graph의 vertex 수 n

2) 그래프를 나타내는 2차원 배열 W (1-indexed)

 

3. Output

1) 지름길을 나타내는 2차원 배열 D (1-indexed)

- D[i][j]는 i번째 vertex에서 j번째 vertex로 가는 지름길의 길이를 나타낸다.

 

4. PseudoCode

void floyd(int n, const number W[][], number D[][]){
    index i, j, k;
    D = W;
    for(k=1 ; k<=n ; k++)
        for(i=1 ; i<=n ; i++)
            for(j=1 ; j<=n ; j++)
                D[i][j] = minimum(D[i][j], D[i][k]+D[k][j]);
}

 

5. Example

class AlgoTest {
    static int inf = Integer.MAX_VALUE;
	
    public static void main(String[] args){
        long[][] W = {{0,1,inf,1,5},{9,0,3,2,inf},{inf,inf,0,4,inf},{inf,inf,2,0,3},{3,inf,inf,inf,0}};
        long[][] D = new long[W.length][W[0].length];
        floyd(W.length, W, D);
        for(int i=0 ; i<D.length ; i++) {
            for(int j=0 ; j<D[i].length ; j++)
                System.out.printf("%2d,",D[i][j]);
            System.out.println();
        }
    }
    // 출력 결과
     0, 1, 3, 1, 4,
     8, 0, 3, 2, 5,
    10,11, 0, 4, 7,
     6, 7, 2, 0, 3,
     3, 4, 6, 4, 0,
    
    static void floyd(int n, long[][] W, long[][] D){
        for(int i=0 ; i<n ; i++)
            D[i] = Arrays.copyOf(W[i], W[i].length);
        for(int k=0 ; k<n ; k++)
            for(int i=0 ; i<n ; i++)
                for(int j=0 ; j<n ; j++)
                D[i][j] = Math.min(D[i][j], D[i][k]+D[k][j]);
    }
}