117. Floyd-Warshall

플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)은 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘으로, 그래프의 정점의 수가 $n$일 때 시간복잡도는 $\Theta(n^3)$이다.

 

플로이드-와샬 알고리즘은 정점들 사이의 최단 거리를 구할 때 중간에 거칠 수 있는 정점의 수를 늘려 나가면서 최단 거리를 갱신하는 방식으로 작동한다. 벨만-포드 알고리즘이 간선을 확인하는 것과는 약간 다르다. 구체적인 작동 방식은 다음과 같다.

    1. 정점 $i$로부터 정점 $j$까지의 최단 거리를 $d_{i, j}$라고 한다.

    2. 각각의 $d_{i, j}$에 대해 $i = j$인 경우 $d_{i, j} = 0$, $i \ne j$인 경우 $d_{i, j} = \infty$로 초기화한다.

    3. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 경우 $d_{x, y}$를 $\min(d_{x, y}, z)$로 바꾼다.

    4. 각각의 정점 $k$에 대해, $d_{i, j}$를 $\min(d_{i, j}, d_{i, k} + d_{k, j})$로 바꾸는 과정을 모든 정점 쌍 $(i, j)$에 대해 수행한다.

 

다익스트라, 벨만-포드 알고리즘에 비해 과정이 복잡하지 않다. 구현 역시 간단하다.

#import<bits/stdc++.h>
using namespace std;
int d[1005][1005];
int main()
{
    int m, n, x, y, z;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i != j)d[i][j] = 1 << 30;
        }
    }
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        d[x][y] = min(d[x][y], z);
    }
    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]);
        }
    }
}

중괄호를 생략할 경우, $3$중 반복문은 훨씬 간단하게 보인다.

    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]);

위 코드의 실행이 끝났을 때 $d_{i, i} < 0$인 경우가 존재한다면 그래프에 음수 사이클이 존재한다고 할 수 있지만, 플로이드-와샬 알고리즘에서는 음수 사이클을 별로 생각하지 않는다. 그래프에 음수 사이클이 존재하지 않고 가중치가 음수인 간선이 존재하는 경우에는 최단 거리를 제대로 찾을 수 있다.

 

또한 $n$이 $1000$ 정도까지 커지더라도 플로이드-와샬 알고리즘은 구조가 간단해서 C 계열 언어 기준으로 $1$초 안에 실행이 된다. 보통 $1$초에 반복문 $10$억 번이 도는 예시로 플로이드-와샬 알고리즘이 많이 사용된다.

 

[연습문제]

 

BOJ 11404. 플로이드 (Gold IV)

가장 기초적인 문제다. 플로이드-와샬 알고리즘으로 정점들 사이의 최단 거리를 모두 구한다.

 

BOJ 2458. 키 순서 (Gold IV)

간선의 가중치를 모두 $1$로 두고 뒤집은 간선의 가중치를 모두 $-1$로 두면 정점에서 다른 모든 정점까지의 거리를 알 수 있는 정점의 개수를 구하는 문제가 된다. 이것은 플로이드-와샬 알고리즘으로 구할 수 있다.

 

BOJ 2273. 줄 서기 (Gold IV)

2458번과 비슷한 문제인데, 간선의 가중치를 $1$과 $-1$로 두는 것까지는 동일하며 이번에는 각각의 정점에서 거리가 양수인 정점의 수와 거리가 음수인 정점의 수를 구하면 문제를 풀 수 있다.

 

BOJ 10159. 저울 (Gold III)

이번에는 각각의 정점에 대해 거리가 $\infty$인 정점의 수를 구하면 된다. 앞의 두 문제보다 한 티어가 높지만 난이도 차이는 거의 없다.

 

BOJ 13314. 플로이드에 오타가? (Gold III)

오타가 난 코드는 $3$중 반복문의 첫 줄에서 비교 연산자 $\le$가 $<$로 되어 있다. 이 반복문은 $k = n$일 때 반복을 실행하지 않는데, 이 반복을 실행하지 않았을 때와 실행했을 때의 최단 거리가 달라진다는 것은 최단 경로가 $n$번째 정점을 반드시 거친다는 의미이므로, $n$번째 정점을 포함하지 않는 서로 다른 두 정점의 쌍 $(n-1)(n-2)$개에 대한 최단 경로가 모두 $n$번째 정점을 반드시 거치게 하면 된다. $n = 100$일 때 $(n-1)(n-2) = 9702$이므로 조건에 맞는다.

 

→ solved.ac tag: floyd_warshall