플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

플로이드-워셜 알고리즘은 그래프에서 모든 점들의 쌍 (u, v) 간의 최단거리를 다 구하는 알고리즘이다.

 

경유점을 다음과 같이 정의하자.

u -> x1 -> x2 -> x3 -> x4 -> v 일때, x1, x2, x3, x4는 경유점.

즉, 어떤 경로에서 시작점과 끝점을 제외한 정점들을 의미한다.

 

이렇게 정의하고, DP 를 사용한다.

k-1번째 루프에서는 1~k-1의 정점들만을 경유점으로 하는 최단경로들의 값을 dp 테이블에 저장한다.

이제, 새로운 정점 k가 들어왔다고 생각하자.

최단거리는 k를 경유점으로 포함하는가, 하지 않는가로 나뉘고, 이는 다음과 같은 점화식으로 표현할 수 있다.

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

따라서 위 점화식으로 $N^3$ 루프를 돌며 계산해주면 된다.

 

여기서 공간복잡도를 $N^3$이 아닌 $N^2$ 으로 할 수 있는데, $dp[k-1][i][k]$와 $dp[k-1][k][j]$만 실제로 사용됨을 이용하면, 1~k-1 까지만 이용해서 i에서 k로 가는 최단거리나, 1~k만 이용하여 i에서 k로 가는 최단거리는 똑같다.

이를 이용하면 슬라이딩 윈도우를 하지 않고도 dp 테이블을 $N^2$ 만 사용하여 채울 수 있다.

for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);

 

음수 간선이 존재할 때, 음수 사이클 판별, 실제 경로 복구와 같은 추가적인 작업들을 할 때에는 주의할 점이 있다.

 

음수 간선이 존재할 경우

$dist[i][j]=min(dist[i][k]+dist[k][j], dist[i][j]);$ 에서 dist[i][k], dist[k][j] 중 하나는 INF 이고, 하나는 음수간선이면 INF 와 INF-1 을 비교하는 꼴이 된다. 이를 방지하기 위하여 dist[i][k]와 dist[k][j]가 모두 INF 가 아닐때만 연산을 해 주어야 한다.

 

최적화

위 조건 dist[i][k], dist[k][j]가 모두 INF가 아니라는 조건을 이용하면 k, i가 결정된 두번째 for문 다음에 INF의 확인을 통해 코드를 최적화할 수 있다.

 

실제 경로 복구

par[i][j] 배열에 i -> j 경로상에 마지막으로 드르는 k 정점을 저장해 논다. 즉, dist가 갱신될 때마다 par도 갱신되면, 그 경로상의 경유점들 중 최대값을 알 수 있고, 만약 모든 par 값들이 주어진다면, 재귀호출을 통하여 실제 경로도 복구할 수 있다.

 

음수 사이클 판별

기본적으로 dist[i][i]=0 이다. 만약에 갱신을 반복하던 중, dist[i][i]가 음수가 된다면 이는 음수 사이클이 존재한다는 점이고, 이로 판별할 수 있다.

 

시간 복잡도 : $O(N^3)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 100;
const int INF = 987654321;

int n, m, s, e;
int dist[MAXN+10][MAXN+10], par[MAXN+10][MAXN+10];
bool negcycle;

void restore(int s, int e)
{
    if(par[s][e]==0) return;
    restore(s, par[s][e]);
    printf("%d ", par[s][e]);
    restore(par[s][e], e);
}

int main()
{
    int i, j, k;
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++) for(j=1; j<=n; j++) dist[i][j]=INF;
    for(i=1; i<=n; i++) dist[i][i]=0;

    for(i=0; i<m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        dist[u][v]=min(dist[u][v], w);
    }

    for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++)
    {
        if(dist[i][k]!=INF && dist[k][j]!=INF)
        {
            if(dist[i][j]>dist[i][k]+dist[k][j])
            {
                dist[i][j]=dist[i][k]+dist[k][j];
                par[i][j]=k;
            }
        }
    }

    for(i=1; i<=n; i++) { for(j=1; j<=n; j++) printf("%d ", dist[i][j]); printf("\n"); }

    while(1)
    {
        scanf("%d%d", &s, &e);
        printf("%d ", s);
        restore(s, e);
        printf("%d\n", e);
    }
}