全点対間最短経路を求めることができるWarshall-Floyd（ワーシャル–フロイド）法を紹介します。
Warshall-Floyd（ワーシャル–フロイド）法
グラフのある1点の頂点から、それ以外のすべての頂点への最短経路は、Dijkstra（ダイクストラ）法で求めることができます。ブログでも何回か紹介しています。
この記事では、すべての頂点から、残りすべての頂点への最短経路を求めることができるWarshall-Floyd（ワーシャル–フロイド）法を紹介します。
配列 dist[i][j] を頂点 i から頂点 j への最短距離とします。dist[i][j] の初期値は、辺の重さが定められている場合はその値とします。定められていない場合は非常に大きい値を設定します。
すべての頂点kに対して、dist[i][k]+dist[k][j]の方が、dist[i][j]より小さければ、この値で更新します。直感的にも分かりやすいアイデアです。
コードとして示すと以下の3重ループとなります。計算量は、頂点数 $N$ に対して、$O(N^3)$ となります。
for (int k = 0; k < v; ++k) {
for (int i = 0; i < v; ++i) {
for (int j = 0; j < v; ++j) {
if ((dist[i][k] < INF)&&(dist[k][j] < INF)) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}dist[i][i]が負の値になれば、グラフは負の閉路を持ちます。
アルゴリズムのテスト
AIZU ONLINE JUDGE で出題されている問題でアルゴリズムをテストします。以下が問題のリンク先です。
GRL 1_C問題 All Pairs Shortest Path
この問題を解くプログラムは以下です。AC判定となります。キーとなるコードの背景色を変更しました。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;
#define INF (1LL << 60)
int main()
{
int v, e;
cin >> v >> e;
vector<vector<ll>> dist(v, vector<ll>(v, INF));
for (int i = 0; i < v; ++i) {
dist[i][i] = 0;
}
for (int i = 0; i < e; ++i) {
int s, t, d;
cin >> s >> t >> d;
dist[s][t] = d;
}
for (int k = 0; k < v; ++k) {
for (int i = 0; i < v; ++i) {
for (int j = 0; j < v; ++j) {
if ((dist[i][k] < INF)&&(dist[k][j] < INF)) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
for (int i = 0; i < v; ++i) {
if (dist[i][i] < 0) {
cout << "NEGATIVE CYCLE" << endl;
return 0;
}
}
for (int i = 0; i < v; ++i) {
for (int j = 0; j < v; ++j) {
if (dist[i][j] == INF) {
cout << "INF" << " \n"[j == v - 1];
} else {
cout << dist[i][j] << " \n"[j == v - 1];
}
}
}
return 0;
}最後に
記事を書くことによって、Warshall-Floyd法の理解を深めることができました。
