플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)

내용을 대략적으로 이해하기에는 여기가 좋다. (구현방법도 단계별로 익히기 좋..다고 생각했는데 다시 읽어보니 왜 항상 최단이 되는지 why에 대한 설명이 좀 부족한 느낌이 드네.. 아래 증명란에서 추가 검토하자)

 

플로이드와샬의 시간복잡도는 심플하게 $O(V^3)$이다. 

N이 2000일때 TLE난적이 있으니 참고하자. 

($2000^3 = 2,000,000,000$, 20억 정도니 2~20초 걸리는거니 당연할지도)

 

PS에서 쓰는 내 소스코드는 다음과 같다.

(백준 11404번 문제의 답안이기도 하다.)

#include <bits/stdc++.h>
using namespace std;
 
//플로이드 와샬
int n, m, u, v, w, in[101][101];
int main()
{
    const int INF = INT_MAX / 4;
    scanf("%d%d", &n, &m);
    //인접행렬만들자
    fill(&in[0][0], &in[n][n], INF);  // 없는간선은 INF
    for (int i = 0; i < n; i++) in[i][i] = 0;  // 자기자신은 0
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        // 간선이 여러개일경우, 최단거리 단선만 기억
        // 이문제의 경우 1-base index라 1빼줌(문제에 따라 다르게 처리)
        in[u - 1][v - 1] = min(in[u - 1][v - 1], w);
    }
    //정점 i > k > j, 핵심로직
    for (int k = 0; k < n; k++)  // 중간정점을 중심으로, 모든 중간정점을 검토함에 주의
    for (int i = 0; i < n; i++)  // 모든 시작정점
    for (int j = 0; j < n; j++)  // 모든 끝정점
        if (in[i][j] > in[i][k] + in[k][j])  // 현재 최단거리보다 K를 거치는게 더 짧으면
            in[i][j] = in[i][k] + in[k][j];  // 업데이트
 
   //결과출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            // 경로를 못찾았을때 이문제는0으로 바꾸는데, 문제에 따른처리 필요
            printf("%d ", in[i][j] < INF ? in[i][j] : 0);
        printf("\n");
    }
    return 0;
}

 

 

아래는 주석제거하고 짧은버전

#include <bits/stdc++.h>
using namespace std;
int n, m, u, v, w, in[101][101];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if(i-j)in[i][j] = 1e9;
    while(m--) scanf("%d%d%d", &u, &v, &w), in[u-1][v-1] = min(in[u-1][v-1], w);
    for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
        in[i][j] = min(in[i][j], in[i][k] + in[k][j]);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) printf("%d ", in[i][j] < 1e9 ? in[i][j] : 0);  
        printf("\n");
    }
    return 0;
}
 

 

 

경로를 출력하는 문제에 대해서는, 여기를 참조하면 어렵지 않게 구현하고 풀 수 있다.

 

증명

많은 인터넷 상의 자료들은 증명에는 별로 관심없고, HOW에만 관심이 있는듯 보인다.

일단 증명에 대한 힌트는 그래도 위키피디아 여기에서 엿볼 수 있는데..

최대 $(|V|^{2})$의 변이 있을 수 있고, 모든 변의 조합을 확인하기 때문이다. 

라는 표현이 있는데, 일견 이해는 되지만, 모든 변의 조합을 1회만 업데이트 하면 옵티멀이 된다는게 뭔가 찜찜하다.

여기에 증명이 나와있는데, 설명이 잘 이해가 안된다. 이 동영상이 그나마 쉽게 접근하고 있는데, 여전히 multiple update가 필요하지 않은 이유에 대해서는 설명이 잘 안된다.

 

어쨌거나, 실제 증명은 다음과 같이 귀납법으로 간단하게 정의된다.

$$\delta^k(i,j)=\begin{cases}
\min\{\delta^{k-1}(i,j),\delta^{k-1}(i,k)+\delta^{k-1}(k,j)\} & \text{for}\,k\geq 1\\
w(i,j) & \text{for}\,k=0\,\text{(i.e., base case)}, 
\end{cases}$$

 

직관적으로는.. k가 0에서 k가 1로 넘어갈때는 확실한데, k가 1에서 2 이상으로 넘어갈때, 기존 업데이트 된 값들이 최대 k번의 연산 이상으로 업데이트가 필요없다는게 잘 이해가 안된다.

 

 

정점 가중치

이 문제를 보면 간선 가중치 뿐 아니라 정점 가중치도 고려해야하는데, 풀어보면 특별히 난이도가 올라가거나 복잡해지진 않았다.

이문제만 그런걸수도 있긴한데, 현재 발견된걸로 그러함.