最短径路全網羅、または、最短径路探索のウォーシャルの方法的拡張(フロイドの方法)



前項の推移閉包は、グラフにおける到達可能性(到達可能か否か)の情報を全ノードペアについて求める方法である『ウォーシャルの方法』についてであった。これは、到達可能性を全ノードペアについて行うことに他ならないが、同様に、任意の2ノード間の最短径路計算を全ノードペアについて行い、その情報を保管することが必要な場合もあり、その場合には、ウォーシャルの方法のアナロジーを2ノード間最短径路問題にあてはめることに通じる。この方法にフロイドの方法という。

今、あるグラフが行列表現してあるとし、エッジの長さが正の数値で記録されている。それがV個のノードからなるグラフがV^2の行列N[i][j], 0<=i<=V-1,0<=j<=V-1,とする。隣接グラフにはエッジがない場合には、未定義である。ノード数Vに関する3重ループにて次のようにして、全ノードペア間の最短距離を情報として有するの行列が得られる。ウォーシャルの方法と同じくノード数による3重ループでO(V^3)である


//本ソースは未検証です
for(i=0;i<V;i++){
for(j=0;j<V;j++){
if(N[i][j]==1){
for(k=1;k<V;k++){
/*
*到達可能判断(ウォーシャルの方法)のときには、%の判断が"==1"であったが
*">0"という判断(到達可能な距離が定められている)に入れ替えられている
*/
if(N[i][k]>0){//%
/*
*#の判断で
*ノード間距離が未定義(N[j][k]!=null)か、
*より短い径路が示唆される(N[j][i]+N[i][k] < N[j][k])かしたら
*/
if(N[j][k]!=null || (N[j][i]+N[i][k] < N[j][k])){//#
/*
*$において『到達可能である(N[j][k]=1)』と更新するかわりに
*距離を更新する
*/
N[j][k]=N[j][i]+N[i][k];//$
}
}
}
}
}