ワーシャルフロイド法は、グラフ上の全点間の最短経路を求めるアルゴリズムです。
本記事ではC++で使えるワーシャルフロイド法のライブラリを実装します。
※なお、今回のライブラリは Graph ライブラリが前提となっています。
以下リンクからコピペしてご使用ください↓
・グラフ構造体 をC++で実装してみた
主な機能と計算量
| 名前 | 説明 | 計算量 |
|---|---|---|
warshall_floyd<T>(g) |
グラフ g に対して、全点間の最短距離を計算 |
$O(V^3)$ |
実装したコード
//------ここにGraphライブラリ-------//
// //
//-------------------------------//
//ret[i][j] := 頂点iからjへの最短距離
template<typename T = long long> // costの型
vector<vector<T>> warshall_floyd(Graph<T> &g){
//初期化
int n = g.size_n();
vector<vector<T>> ret(n, vector<T>(n, T(100100100100100100)));
for(int i=0;i<n;i++){
ret[i][i] = 0;
for(pair<T,int> &next: g.nexts(i)){
ret[i][next.second] = next.first;
}
}
//各頂点間の最短経路を計算
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j]);
}
}
}
return ret;
}
使用例
#include<bits/stdc++.h>
using namespace std;
//------ここにGraphライブラリ-------//
// //
//-------------------------------//
//--ここにWarshall-Floydライブラリ--//
// //
//-------------------------------//
int main(void){
// グラフの作成
Graph g(4);
g.add_edge(10, 0, 1); //0 → 1：コスト10の辺を追加
g.add_edge(10, 0, 2); //0 → 2：コスト10の辺を追加
g.add_edge(15, 0, 3); //0 → 3：コスト15の辺を追加
g.add_edge(1, 2, 3); //2 → 3：コスト1の辺を追加
// 各頂点間の最短距離を求める
vector<vector<long long>> w = warshall_floyd(g);
cout << w[0][3] << endl; // 11
}
注意点・Tips
- 頂点番号は
0-indexedで扱っています - コストの型
Tには、long long、int、doubleなどが使えます -
infの意味で100100100100100100が出てきますが、コストの型を変える際は適宜変更してください - 無向グラフは辺
u → vと辺v → uの両方を追加する必要がります - 負閉路がある場合は
w[i][i] < 0となるので、それをチェックすると検出できます
実際に使ってみる
AtCoder Beginner Contest 012 - D問題
#include <bits/stdc++.h>
using namespace std;
//------ここにGraphライブラリ-------//
// //
//-------------------------------//
//---ここにWarshall-Floydライブラリ---//
// //
//---------------------------//
// グローバル変数
int N, M;
int main(void){
// 入力
cin >> N >> M;
// グラフを構築
Graph g(N);
for(int i=0;i<M;i++){
int a, b, c;
cin >> a >> b >> c;
a--; // 0-indexedに変換
b--; // 0-indexedに変換
g.add_edge(c, a, b);
g.add_edge(c, b, a);
}
//各間の往復の最短経路を計算
vector<vector<long long>> w = warshall_floyd(g);
//最短経路が最も離れている2点を計算
long long ans = 100100100100100100LL;
for(int i=0;i<N;i++){
// 場所iに住んだ時の最悪ケース
long long warst = 0;
for(int j=0;j<N;j++){
warst = max(warst, w[i][j]);
}
//最悪ケースの最小を取る
ans = min(ans, warst);
}
cout << ans << endl;
}