フロイドワーシェルアルゴリズム

Floyd-Warshallアルゴリズムは、動的計画法を使用して、負の重みを持つサイクルのない重み付きグラフのすべての頂点間の最短距離を見つけるためのアルゴリズムです。 これは基本的なアルゴリズムなので、それを知っている人はこれ以上読むべきではありません。



このアルゴリズムは、1962年にRobert FloydとStephen Warshallの記事で同時に公開されましたが、 Bernard Royは1959年にほぼ同じアルゴリズムを公開しましたが、気付かれることはありませんでした。

発言

グラフに負の重みを持つエッジが含まれていない場合、この問題を解決するために、ダイクストラアルゴリズムを使用して、 1つの頂点から他のすべての頂点までの最短パスを見つけ、各頂点で実行できます。 このようなアルゴリズムの動作時間は、ダイクストラアルゴリズムに使用するデータのタイプによって異なります。単純な優先度キューまたはバイナリまたはフィボナッチヒープのいずれかであり、動作時間はO（V ³ ）からO（V * E * log（V））、Vは頂点の数、Eはエッジです。 （ 「ああ」は素晴らしいです ）。



負の重みを持つエッジがある場合、Bellman-Fordアルゴリズムを使用できます。 しかし、グラフのすべての頂点で実行されるこのアルゴリズムはより遅く、その動作時間はO（V ² * E）であり、非常に「厚い」グラフではO（V ⁴ ）です。

動的プログラミング

動的アルゴリズムとはどういう意味ですか？ 動的計画法は、額法、つまり総当たり攻撃または貪欲アルゴリズムによる問題解決の代替手段です 。 元の問題を解決するために、より小さなサブタスクの最適なソリューションを使用できる場合に使用されます。 一般に、メソッドは次のようになります。



1.タスクをより小さなサブタスクに分割します。

2.サブタスクの最適な解決策を見つけることは再帰的です。

3.取得したサブタスクのソリューションを使用して、元の問題のソリューションを構築します。



グラフのすべての頂点間の最短経路を見つけるには、すべての可能性を列挙するのではなく、時間が長くなり、より多くのメモリが必要になりますが、上向きの動的プログラミング、つまり、元の問題を解決するために後で必要なすべてのサブタスクが事前に計算されて使用されます

最短経路構造

このアルゴリズムは、グラフの最短パスの2つのプロパティに基づいています。 最初：



頂点v ₁から頂点v _kへの最短パスp _1k =（v ₁ 、v ₂ 、...、v _k ）とそのサブパスp '（v _i 、v _{i + 1} 、...、v _j ）がありますが、行為1 <= i <= j <= k。

pがv ₁からv _kへの最短経路である場合、p 'は頂点v _iからv _jへの最短経路でもあります。

これは、パスpのコストがパスpのコストと残りの部分のコストの合計であるため、簡単に証明できます。 したがって、より短いパスp 'があることを想像して、この量を減らします。これは、この量がすでに最小だったという記述と矛盾することになります。



2番目のプロパティは、アルゴリズムの基礎です。 1からnまでの番号が付けられた頂点{v ₁ 、v ₂ 、...、v _n }と、インデックスkで区切られた特定の許容頂点のセットを通過するv _iからv _jへのパスp _ijを持つグラフGを考えます。



つまり、k = 0の場合、許容される中間頂点のセットは初期ゼロであるため、頂点の相互直接接続を考慮します。 k = 1の場合、頂点v ₁を通過するパスを考慮します。k= 2の場合、頂点{v ₁ 、v ₂ }を通過し、k = 3-{v ₁ 、v ₃ 、v ₃ }を通過します。



たとえば、このようなグラフ（左）とk = 1があります。つまり、ノード「1」のみが中間ノードとして許可されます。 このグラフでは、k = 1の場合、パスp ₄₃はありませんが、k = 2の場合、「2」または「1」と「2」を介して「4」から「3」に到達できます。



コストd _ijの許容される中間頂点{1..k-1}を持つ最短経路p _ijを考えます。 次に、許可された頂点のセットが{1..k}になるように、セットをk番目の要素に拡張します。 この拡張機能では、2つの結果が可能です。



ケース1.要素kは最短経路p _ijに含まれていません 。つまり、頂点を追加しても何も勝たず、何も変更していません。つまり、最短経路d ^k _ijのコストはそれぞれ変更され_ていません。

d ^k _ij = d ^k-1 _ij -kが増加するまで値を引き継ぎます。

ケース2。要素kが最短パスp _ijに入ります。つまり、新しい頂点を許可されたパスに追加した後、最短パスが変更され、頂点v _kを通過します。 新しい方法はいくらですか？



新しい最短パスは頂点v _kによってp _ikとp _kjに分割され、最初のプロパティを使用します。それに応じて、p _ikとp _{kjはそれぞれ} v _iからv _kおよびv _kからv _jの最短パスでもあります。 手段



d ^k _ij = d ^k _ik + d ^k _kj



そして、これらのパスのkは最終ノードまたは初期ノードであるため、中間ノードのセットには含まれないため、そこから削除できます。

d ^k _ij = d ^k-1 _ik + d ^k-1 _kj

アルゴリズム

両方のケースでd ^k _ijの値を見てみましょう-右！ どちらの場合も、k-1のd値の合計です。つまり、dの初期値（k = 0）があれば、後続のすべてのk値についてdを計算できます。 そして、k = 0のd値を知っています。これは、グラフのエッジ、つまり中間ノードのない化合物の重み/コストです。



k = n（nは頂点の数）の場合、頂点のすべてのペアに対してdの最適値を取得します。



k-1からkに増加するとき、d ^k _ikに対してどの値を保持しますか？ ケース1および2の最小値により、つまり、古いパスまたは追加の頂点を追加したパスの方が安価であるかどうかを調べます。

擬似コード

最後に、アルゴリズム自体。 グラフ表現を隣接行列として使用します。







ご覧のとおり、アルゴリズムは非常に単純です-最初に最短距離行列D ⁰が初期化され、最初は隣接行列と一致します。サイクルではkの値を増やし、距離行列を再計算します。D0からD ¹ 、D ¹ -D ²など= n。



2つの頂点の間にエッジがない場合、隣接行列に大きな数が書き込まれたと想定されます（このグラフの任意のパスの長さよりも大きいほど十分に大きい）。 このエッジは常に不利になり、アルゴリズムは正しく機能します。 ただし、特別な対策が講じられていない場合、エッジのグラフに負の重みがある場合は、∞-1、∞-2などの形式の数字、もちろん、対応するピークにはまったく方法がありません。 したがって、グラフにネガティブエッジがある場合、既に「方法がない」状態からの遷移を実行しないように、フロイドアルゴリズムを記述することをお勧めします。

例

行列の最初の再計算-1つの値が変更され、許可された頂点のセットが頂点「1」に拡張されたため、安価な方法で頂点「4」から「2」に到達できました。



d ^k _ij = min（d ^k-1 _ij ; d ^k-1 _ik + d ^k-1 _kj ）



d ¹ ₄₂ = min（d ⁰ ₄₂ 、d ⁰ ₄₁ + d ⁰ ₁₂ ）



d ¹ ₄₂ =最小（4、-1）



2回目の反復、p _43の改善された値







結果







あちこちでアプレットを試して、アルゴリズムが実際にどのように機能するかを確認できます。

稼働時間とメモリ使用量の分析

このアルゴリズムでは、行列を格納するためにO（n ³ ）メモリが必要です。 ただし、d ^k _ijからインデックスkを削除することにより、不要なマトリックスを書き換えたり、2次元マトリックスに変更するたびに、マトリックスの数を簡単に2に減らすことができます。 最も頻繁に使用される最良のオプションは、隣接行列に直接書き込むことです。追加のメモリはまったく必要ありませんが、元の行列をすぐに書き換える場合は、アルゴリズムの正しさをさらに示す必要があります。従来の学術的証明は、前の反復の行列変わりません。



動作時間に関しては、1〜n-Θ（n ³ ）の3つのネストされたサイクル。

負のサイクルの場合

グラフに負の重みのサイクルが含まれている場合、正式には、Floyd-Warshallアルゴリズムはそのようなグラフには適用できません。 しかし、実際には、アルゴリズムは、パスが負の値のサイクルをたどらないすべてのカップルに対して正しく機能し、残りについては、おそらく非常に負の数を取得します。 このアルゴリズムは、-∞に対応するこのようなペアの値を導出するように教示できます。



ところで、そのようなグラフを作成した後、負の数が最短パスマトリックスの対角線に表示されます-このサイクルの頂点からそれ自体までの最短距離はゼロより小さくなり、これはこのサイクルの通過に対応するため、アルゴリズムを使用してグラフ内の負のサイクルの存在を判断できます。

道の再建

距離行列は、頂点のペアの最短（最も短い）距離を示しますが、パスをどのように知っていますか？ 非常に簡単で、d ^k _ijを計算する場合、 _{πk ij}も計算する必要があります。 この場合のπk ijは、許可された中間頂点のセット{1..k}を持つv _iからのパス上の頂点v _jの前身です。



ここに置いておきます。他の人が自分で考えることができます

申込み

基本的なアルゴリズムと同様に、Floyd-Warshallアルゴリズムは非常に広く使用されており、グラフの推移的閉包の検索から始まり、遺伝学とプロジェクト管理で終わります。 しかし、最初に頭に浮かぶのは、もちろん、トランスポートと他のあらゆる種類のネットワークです。



たとえば、都市の地図を撮影すると、その交通システムはグラフであり、帯域幅やその他の重要なパラメーターから計算されたコストを各エッジに割り当てます。仲間の旅行者を最短/最速/最安のルートに連れて行くことができます。











<sub>それはすべて、あまり書かれていませんので、エラー、矛盾、誤解などを指摘した場合、感謝します、私はまだこのテキストが必要です:)



訂正してくれたRustam 'y and mastersobg 'に感謝</sub>