[알고리즘] All-Pairs Shortest Path, Floyd Warshall Algorithm

모든 가능한 노드의 쌍의 Shortest Path를 구하는 방법?
단순히 다익스트라를 N번 돌리는 방법이 있다.
최악의 경우 O(N^2logN), 보통은 O(Nx(N+M)logN) <= N^3logN

그리고 다른 방법은 DP 아이디어를 사용한 Floyd Warshall Algorithm이 있다.

Floyd Warshall Algorithm

어떠한 노드 i와 j로 가는 최단 경로를 구할 때 경유하는 노드에 초점을 두어서, 그 노드를 경유해가는 것이 기존 경로보다 더 빠르다면 기존 경로를 업데이트 한다.

아이디어

• 1부터 N까지 번호가 붙은 노드들이 있다.
• 오로지 {1,2,3,...,k}를 통해서 가는 모든 가능한 i부터 j까지의 Shortest Path를 찾는다.
• k는 0부터 N까지 점점 늘리면서 수행한다.

답이 적은 것부터 계산하는 DP이다.
일부분의 노드를 통해서만 가는 Shortest Path를 구한다.

• D[k][i][j]는 Shortest Path length의 값을 나타낸다.
• D[k-1][i][j] 값을 통해 D[k][i][j]을 계산한다.
• 초기값은 D[0][i][j]이고 i부터 j로 가는 Direct Path를 나타낸다.

다음 중 더 짧은 Length를 가진 것이 답이다

• 노드 k를 쓰지 않은 Direct Path인 D[k-1][i][j]
• 노드 k를 거쳐가는 Path인 D[k-1][i][k] + D[k-1][k][j]

Pseudo Code

int D[n+1][n+1][n+1];

int F(int W[n+1][n+1], int n)
{
	for(int i=1; i<=n; i++)
    {
    	for(int j=1; j<=n; j++)
        {
        	D[0][i][j] = W[i][j]; // Direct Path 초기치 셋팅 
        }
    }
    
    for(int k=1; k<=n; k++)
    {
    	for(int i=1; i<=n; i++)
        {
        	for(int j=1; j<=n; j++)
            {
            	D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j]);
            }
        }
    }
}

D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j]);
위 코드가 이 DP 문제의 점화식이다.
D[k][i][j]는 우리가 구할 i부터 j까지의 Shortest Path Length가 들어갈 것이라고 정했었다.
따라서 해당 값은 D[k-1][i][j] 이라는 지금까지 추적해왔던 min Length이거나,
지금 차례의 k를 거쳐가는 i부터 j까지의 Length 중 최소값이 되는 것이다.

시간복잡도는 3중 for문을 사용하고 있어서 O(N^3)이다.
N은 노드의 개수이다.

더 적은 메모리를 사용하는 방법 #1

위 코드에서 최소값을 계속해서 추적하기 때문에 바로 이전인 k-1의 최소값만
확인하면 된다는 점을 이용하면 메모리를 줄일 수 있다.

int D[2][n+1][n+1]; // n+1에서 2로 줄였음

int F(int W[n+1][n+1], int n)
{
	for(int i=1; i<=n; i++)
    {
    	for(int j=1; j<=n; j++)
        {
        	D[0][i][j] = W[i][j]; // Direct Path 초기치 셋팅 
        }
    }
    
    for(int k=1; k<=n; k++)
    {
    	for(int i=1; i<=n; i++)
        {
        	for(int j=1; j<=n; j++)
            {
            	D[k%2][i][j] = min(D[(k-1)%2][i][j], D[(k-1)%2][i][k] + D[(k-1)%2][k][j]);
            }
        }
    }
}

더 적은 메모리를 사용하는 방법 #2

앞에서 D[k-1][i][k] + D[k-1][k][j] 을 계산했었는데,
이후 값을 계산할 때에도 한 쪽이 k인 것만 재사용될 것이다.따라서 N^2의 배열로 해결할 수 있다.

int D[n+1][n+1];

int F(int W[n+1][n+1], int n)
{
	for(int i=1; i<=n; i++)
    {
    	for(int j=1; j<=n; j++)
        {
        	D[i][j] = W[i][j];
        }    
    }
    
    for(int k=1; k<=n; k++)
    {
    	for(int i=1; i<=n; i++)
        {
        	for(int j=1; j<=n; j++)
            {
            	D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
            }
        }
    }
}

연습문제

Q. 위 알고리즘을 써서 i에서 j로 가는 Shortest Path를 구했는데,
어떤 a와 b노드 사이의 엣지 w을 추가하여 다시 계산하려면 O(N^3)보다 짧은 시간에 구할 수 있을까?

A. w를 사용하지 않은 Shortest Path는 이미 알고 있으므로
min(이미 알고 있는 경로, w엣지를 포함한 경로)만을 계산하면 된다.