All pairs Shortest path Problem - Floyd Warshall Algorithm.

All pairs Shortest path(ASP) Problem - 모든 쌍에 대한 최단 거리을 구하는 문제.

 

Floyd Warshall Alogrithm은 ASP 이다. 이를 DP로 구현해보도록 하자.

 

Vertex가 n개가 있고(V1, V2, .... , Vn), Directed, weighted graph이고, 이때 weight는 nonnegative 하다. 

 

/// Matrix W ///

* i -> j 인 path가 있으면 그 path의 weight를 입력한다. W[i, j] = weight of path i -> j

* i -> j 인 path가 없으면 무한대 값을 입력한다. W[i, j] = ∞

* i -> i 이거나 j -> j 인 path는 0을 입력한다. W[i, j] = 0

 

/// Matrix D ///

* i -> j로 가는 최단 거리 값을 입력한다. D[i, j] = weight of shortes path i -> j

* 이때, k라는 새로운 변수가 등장한다. k는 지나는 것을 고려해야하는 vertex를 뜻한다.

* k = 0 이라면, D[i, j] = W[i, j] 이다. (지나는 것을 고려해야하는 vertex가 없음으로)

* k = 1, 2, 3, ..... , n 이라면, k개의 vertex를 지나는 것을 고려하면서 나온 최단 경로 값을 입력해야한다.

* 이 과정을 하기위해 i -> k 와 i -> j 로 나누어 계산한다. 이는 i -> k와 k -> j 둘다 최단 거리이면, i -> j 도 최단 거리이기 때문이다. (이 원리로 Principle of Optimality (최적성의 원칙)을 만족하여 DP를 사용할 수 있다)

* i -> j 로 가는 것과 k를 거처서 가는 [i -> k] + [i -> j] 를 비교했을 때 더 작은 값을 갱신한다.

 

/// Matrix P ///

* Matrix D에서 최단 경로를 찾았을 때 k의 값을 입력한다. 이는 최단 경로를 출력할 떄 사용된다.

 

위의 내용을 바탕으로 Pseudocode를 짜보면

모든 Vertex 사이의 최단 거리 구하기.

void FloydWarshall(n, W[][], D[][]. P[][])
{
	 i, j, k;
     
     for(i = 1; i <= n; i++)				// Matrix P 초기화
     	for(j = 1; j <= n; j++)
        	P[i][j] = 0;
     
     D = W; // Matrix D를 Matrix W로 초기화
     
     for(k = 1; k <= n; k++)
     	for(i = 1; i <= n; i++)
        	for(j = 1; j <=n; j++)
            	if(D[i][k] + D[k][j] < D[i][j]){	//i -> j의 거리보다 i-> k + k -> j 의 거리가 작다면
                	P[i][j] = k;
                    D[i][j] = D[i][k] + D[k][j];
                }		// else의 경우, 바뀌는 것이 없다.
}

===========================================================================

구한 최단 경로 출력

void path(i, j)
{
	if(P[i][j] != 0){
   	path(i, P[i][j]);	// i -> k
    	cout << P[q][r];	// k 출력
    	path(P[i][j], j);	// k -> j
	}
}

// 모든 Vertex 사이의 최단 거리를 구했기 때문에 가능. Priciple of Optimality

시간 복잡도 : theta(Cube n)

공간 복잡도 : theta(Cube n)

 

<소스코드>

// 편의상 Vertex의 개수는 5로 가정하고, Input()은 생략.

#include <iostream>
#include <algorithm>

#define SIZE 6

using namespace std;

int W[SIZE][SIZE];
int D[SIZE][SIZE];
int P[SIZE][SIZE];
int n = 5;

void FloydWarshall(){
    int i, j, k;

    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){
            P[i][j] = 0;
        }
    }

    copy(&W[1][1], &W[1][1] + (SIZE * SIZE), &D[1][1]);

    for(k = 1; k <= n; k++){
        for(i = 1; i <= n; i++){
            for(j = 1; j <= n; j++){
                if(D[i][k] + D[k][j] < D[i][j]){
                    P[i][j] = k;
                    D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
    }
}

void path(int s, int e){
    if(P[s][e] != 0){
        path(s, P[s][e]);
        cout << P[s][e];
        path(P[s][e], e);
    }
}


int main()
{
    int s, e;

    cout << "그래프 입력" << '\n';

    Input();			// W[][]에 값 입력
    FloydWarshall();

    cout << "시작점과 도착점 입력" << '\n';
    cin >> s >> e;

    path(s, e);

    return 0;
}

끝.

틀린 부분 지적 환영합니다.