Floyd最短パスアルゴリズム
Floyd-Warshallアルゴリズム
(Floyd-Warshall algorithm)は任意の2点間を解決する最短経路である
アルゴリズム
、有向図を正しく処理できる
あるいは負の重みの最短経路問題であり,図への伝達閉パケットの計算にも用いられる.
1つの図の重み行列により,その2点間の最短経路行列を求めた.
図の重み付き隣接行列A=[a(i,j)]n×nから、n回の更新が再帰的に行われ、すなわち、マトリクスD(0)=Aから、1つの式に従ってマトリクスD(1)が構築される.また同じ式でD(1)からD(2);......;最後に,同じ式を用いてD(n−1)から行列D(n)を構築した.マトリクスD(n)のi行j列要素は、i番頂点からj番頂点までの最短経路長であり、D(n)を図の距離マトリクスと呼ぶとともに、2点間の最短経路を記録するために後続ノードマトリクスpathを導入することもできる.
iとjの間の他のすべての点を1回緩和する(緩和技術)を用いた.従って時間複雑度はO(n^3);
集合中のノードのみを中間ノードとする最短パスの長さにする.
最短経路が点kを通過すると、
最短経路が点kを通らなければ.
だから、.
その状態遷移方程式は以下の通りである:D[i,j]:=min{
D[i,j],D[i,k]+D[k,j]}
map[i,j]はiからjまでの最短距離を表し,Kは窮屈である.
i,jのブレークポイント,D[n,n]の初期値は0であるか,あるいはテーマの意味に従って行うべきである.
もちろん、この道が通っていなければ、D[i,k]という道がないなど、特殊な処理が必要です.
Floyd−Warshallアルゴリズムの時間的複雑度は空間的複雑度である.
Floyd-Warshallアルゴリズムの説明は次のとおりです.
ここでは、点から点への代価を表し、∞は2点間に接続がないことを示す.
実際のアルゴリズムでは,空間を節約するために,元の空間で直接反復することができ,空間を2次元に下げることができる.
大まかなコードは次のとおりです.
それと同時に、ans[k-1][i][j]の値によってans[k][i][j]の値を推定すると、すべてのans[k][i][j]の値はans[k-1][i][j]とans[k-1][i][k]+ans[k-1][k][j]との大きさ関係によって決定されるが、同時にans[k][i][k]とans[k][k][j]はans[k][k][j]とans[k][k][j]とans[k][k][j]とans[k-1][k][j]の値と必ず同じであることに気づき、つまり、これらの値は今回の更新によって変化しません.コードを次のように簡略化します.
(Floyd-Warshall algorithm)は任意の2点間を解決する最短経路である
アルゴリズム
、有向図を正しく処理できる
あるいは負の重みの最短経路問題であり,図への伝達閉パケットの計算にも用いられる.
1つの図の重み行列により,その2点間の最短経路行列を求めた.
図の重み付き隣接行列A=[a(i,j)]n×nから、n回の更新が再帰的に行われ、すなわち、マトリクスD(0)=Aから、1つの式に従ってマトリクスD(1)が構築される.また同じ式でD(1)からD(2);......;最後に,同じ式を用いてD(n−1)から行列D(n)を構築した.マトリクスD(n)のi行j列要素は、i番頂点からj番頂点までの最短経路長であり、D(n)を図の距離マトリクスと呼ぶとともに、2点間の最短経路を記録するために後続ノードマトリクスpathを導入することもできる.
iとjの間の他のすべての点を1回緩和する(緩和技術)を用いた.従って時間複雑度はO(n^3);
集合中のノードのみを中間ノードとする最短パスの長さにする.
最短経路が点kを通過すると、
最短経路が点kを通らなければ.
だから、.
その状態遷移方程式は以下の通りである:D[i,j]:=min{
D[i,j],D[i,k]+D[k,j]}
map[i,j]はiからjまでの最短距離を表し,Kは窮屈である.
i,jのブレークポイント,D[n,n]の初期値は0であるか,あるいはテーマの意味に従って行うべきである.
もちろん、この道が通っていなければ、D[i,k]という道がないなど、特殊な処理が必要です.
Floyd−Warshallアルゴリズムの時間的複雑度は空間的複雑度である.
Floyd-Warshallアルゴリズムの説明は次のとおりです.
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
if () then
← ;
ここでは、点から点への代価を表し、∞は2点間に接続がないことを示す.
実際のアルゴリズムでは,空間を節約するために,元の空間で直接反復することができ,空間を2次元に下げることができる.
大まかなコードは次のとおりです.
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(ans[k-1][i][k]== ||ans[k-1][k][j]== )
{
ans[k][i][j]=ans[k-1][i][j]; // ， i j k k-1
continue;
}
if(ans[k-1][i][j]== ||ans[k-1][i][k]+ans[k-1][k][j]<ans[k-1][i][j])
{
ans[k][i][j]=ans[k-1][i][k]+ans[k-1][k][j];
}
else
{
ans[k][i][j]=ans[k-1][i][j];
}
}
}
}それと同時に、ans[k-1][i][j]の値によってans[k][i][j]の値を推定すると、すべてのans[k][i][j]の値はans[k-1][i][j]とans[k-1][i][k]+ans[k-1][k][j]との大きさ関係によって決定されるが、同時にans[k][i][k]とans[k][k][j]はans[k][k][j]とans[k][k][j]とans[k][k][j]とans[k-1][k][j]の値と必ず同じであることに気づき、つまり、これらの値は今回の更新によって変化しません.コードを次のように簡略化します.
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(ans[i][k]== ||ans[k][j]== ) continue;
if(ans[i][j]== ||ans[i][k]+ans[k][j]<ans[i][j])
{
ans[i][j]=ans[i][k]+ans[k][j];
}
}
}
}