Warshall Floyd
コードについての説明
全点対間の最短経路問題(APSP) を高速に解くアルゴリズム. $j$ から $k$ への最短距離 $d[j][k]$ は $\underset{i}{\min} (d[j][i] + d[i][k])$ と等しいことを用いている. また min-plus 代数上での隣接行列の積と見ることもできる.
全点対間の最短経路問題をこのアルゴリズムより速いオーダー(正確には $\O (n^{2.99...})$) で求めることは難しいと考えられている(ASAP conjecture).
時間計算量: $\O (n^3)$
コード
#define MAX_V 100
// d[i][j] は INF 初期化したあと
// i → j に重み cost の辺が存在するなら d[i][j] = cost のように代入しておく
int d[MAX_V][MAX_V];
void warshall_floyd(int V)
{
for(int i = 0; i < V; i++){
d[i][i] = 0;
}
for(int i = 0; i < V; i++){
for(int j = 0; j < V; j++){
for(int k = 0; k < V; k++){
d[j][k] = min(d[j][k],d[j][i]+d[i][k]);
}
}
}
}
verify 用の問題
Atcoder : アットコーダー王国の交通事情 提出コード