[algorithm] Floyd-Warshall

플로이드-워셜 알고리즘은 음의 가중치가 있는 그래프에서 모든 노드에서 모든 노드까지의 최단 경로를 찾는 알고리즘이다.

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

위의 그래프를 인접 행렬로 표현하면 아래와 같다.

	0	1	2	3
0	0	4	-1	8
1	INF	0	-2	-10
2	INF	INF	0	3
3	INF	INF	INF	0

#include <iostream>
#include <vector>
using namespace std;

#define INF (int)1e9

void floyd_warshall(vector<vector<int>>& v, vector<vector<int>>& dist) {
    dist = v;
    for (int k = 0; k < v.size(); k++) {
        for (int i = 0; i < v.size(); i++) {
            for (int j = 0; j < v.size(); j++) {
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]);
            }
        }
    }
}

int main() {
    vector<vector<int>> v{
        { 0, 4, -1, 8 },
        { INF, 0, -2, -10},
        { INF, INF, 0, 3 },
        { INF, INF, INF, 0 }
    };
    vector<vector<int>> dist(v.size(), vector<int>(v.size(), 0));

    floyd_warshall(v, dist);
    for (int i = 0; i < dist.size(); i++) {
        for (int j = 0; j < dist[i].size(); j++) {
            cout << dist[i][j] << "\t";
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}