플로이드 알고리즘

모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘

• 그래프가 방향/무방향 그래프인지는 상관 없음
• 간선의 값이 음수여도 잘 동작하지만 음수인 사이클이 있으면 문제 발생

알고리즘

1. 최단거리 테이블을 초기화
   • 자기 자신으로 가는 cost = 0, 갈 수 없는 cost = INF
2. 현재 테이블에서 1번 정점을 거쳐가는 최단 거리만을 먼저 갱신
   • s에서 t로 D[s][t]보다 D[s][1] + D[1][t]가 작을 경우 갱신

#include <bits/stdc++.h>
using namespace std;
​
const int INF = 0x3f3f3f3f;
int d[105][105];
int n, m;
​
int main(void) {
    cin.tie(0);
    cin.sync_with_stdio(0);
​
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        fill(d[i], d[i]+1+n, INF);    // 모든 행렬 값을 INF로 초기화​​
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }
    for(int i = 1; i <= n; i++) d[i][i] = 0;
​
    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]);
    ​
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(d[i][j] == INF) cout << "0 ";
            else cout << d[i][j] << ' ';
        }
        cout << '\n';
    }
}

• 많이 쓰던 0x7f7f7f7f7f 대신 0x3f3f3f3f를 쓰는 이유는 플로이드 알고리즘 계산 과정에서 INF 값 2개를 더하는 일이 발생할 수 있는데 그 때 int overflow가 나지 않게 하기 위해서이다.
  ​
• 정점이 1000개일 때 $O(n^3)$으로 돌아가서 1,000,000,000, 즉 10억이라 플로이드 알고리즘을 쓸 수 없겠다 싶을 수 있지만, 플로이드 알고리즘은 단순 사칙 연산이 주를 이루고 있기 때문에 정점 1000개 까지는 플로이드 알고리즘으로 풀어볼 만 하다.
  ​
• 그냥 min 함수를 써서 매번 대입을 하는 것보다 if(d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j]로 작성해 갱신이 꼭 필요할 때에만 대입이 일어나도록 하는 것이 시간상 유리하다.
• 이러한 상수 시간 최적화가, 연산량이 10억번씩으로 많은 플로이드 알고리즘에서는 효과가 뛰어나다.

  따라서 상수 시간의 차이로 인해 문제를 맞고 틀리고가 결정될 수 있기 때문에 보통 1000개씩 주진 않는다.