Warshall-Floyd
(Graph/WarshallFloyd.cpp)

• View this file on GitHub
• Last update: 2021-06-18 20:59:19+09:00

説明

重み付き（有向）グラフにおける全頂点間の最短距離を求める。

• vector<vector<long long>> WarshallFloyd(int N,vector<vector<long long>> dist) : dist[i][j] = 頂点iと頂点jを結ぶ辺の距離（ただしiとjの間に辺が存在しないならばINF）である頂点数がNのグラフに対して、全頂点間の最短距離を求める。返り値は2次元配列に格納される（ただし頂点間に経路が存在しないならばINF）。計算量 $O(N^3)$

tips : このアルゴリズムは負の辺でも動作する。返り値の配列をretとすると、ret[i][i] < 0となるiが存在するならばグラフには負閉路が含まれている。

Verified with

• Test/AOJ/WarshallFloyd.test.cpp

Code

vector<vector<long long>> WarshallFloyd(const int& N,const vector<vector<long long>> dist) {
    vector<vector<long long>> ret = dist;
    for(int k = 0;k < N;k++) {
        for(int i = 0;i < N;i++) {
            for(int j = 0;j < N;j++) {
                if(ret[i][k] != INF && ret[k][j] != INF) {
                    chmin(ret[i][j],ret[i][k] + ret[k][j]);
                }
            }
        }
    }
    return ret;
}

#line 1 "Graph/WarshallFloyd.cpp"
vector<vector<long long>> WarshallFloyd(const int& N,const vector<vector<long long>> dist) {
    vector<vector<long long>> ret = dist;
    for(int k = 0;k < N;k++) {
        for(int i = 0;i < N;i++) {
            for(int j = 0;j < N;j++) {
                if(ret[i][k] != INF && ret[k][j] != INF) {
                    chmin(ret[i][j],ret[i][k] + ret[k][j]);
                }
            }
        }
    }
    return ret;
}

Back to top page