ジョンソンのアルゴリズム

ジョンソンのアルゴリズム
クラス	全ペア最短経路問題（重み付きグラフの場合）
データ構造	グラフ
最悪の場合のパフォーマンス

ジョンソンのアルゴリズムは、辺に重み付けされた有向グラフのすべての頂点のペア間の最短経路を見つける方法です。一部の辺の重みは負の数にすることができますが、負の重みのサイクルは存在してはいけません。ベルマンフォードアルゴリズムを使用して、入力グラフからすべての負の重みを削除する変換を計算し、変換されたグラフでダイクストラのアルゴリズムを使用できるようにします。^[1]^[2]このアルゴリズムは、1977年に最初にこの手法を発表したドナルド・B・ジョンソンにちなんで名付けられました。 ^[3]

同様の再重み付け手法は、エドモンズとカープによる最小コストフロー問題に対する逐次最短経路アルゴリズムのバージョンでも使用されている[ ⁴ ]。また、非負の辺重みを持つグラフ内の同じ2つの頂点間の全長が最小の2つの互いに素な経路を見つけるためのスールバールのアルゴリズムでも使用されている^{[5] 。}

アルゴリズムの説明

ジョンソンのアルゴリズムは以下のステップから構成される: ^[1]^[2]

まず、新しいノード $q$ がグラフに追加され、ゼロ重みエッジによって他の各ノードに接続されます。
次に、ベルマン・フォードアルゴリズムを使用して、新しい頂点 $qから始めて、各頂点$ $vについて$ $qから$ $v$ へのパスの最小重み $h (v)$ を見つけます。このステップで負のサイクルが検出されると、アルゴリズムは終了します。
次に、ベルマンフォードアルゴリズムによって計算された値を使用して、元のグラフのエッジの重みが再調整されます。つまり、長さ⁠ ⁠ を持つ $uから$ $v$ へのエッジに、新しい長さ $w$ $($ $u$ $,$ $v$ $) +$ $h$ $($ $u$ $) -$ $h$ $($ $v$ $)$ が与えられます。 $w(u,v)$
最後に、 $q$ が削除され、ダイクストラのアルゴリズムを使用して、各ノード $s$ から再重み付けされたグラフ内の他のすべての頂点への最短経路が検索されます。次に、ダイクストラのアルゴリズムによって返された距離に $h$ $($ $v$ $) -$ $h$ $($ $u$ $)$ を加算して、各距離 $D$ ( $u$ , $v$ ) について元のグラフの距離が計算されます。

例

ジョンソンのアルゴリズムの最初の 3 つの段階が下の図に示されています。

図の左側のグラフには、負のエッジが 2 つありますが、負のサイクルはありません。中央のグラフには、新しい頂点 $q 、$ $q$ を開始頂点としてベルマンフォードアルゴリズムによって計算された最短経路ツリー、および $q$ からそのノードまでの最短経路の長さとして他の各ノードで計算された値 $h (v) が表示されています。$ $q$ には各頂点への長さが 0 のエッジがあり、最短経路はそのエッジより長くすることはできないため、これらの値はすべて非正であることに注意してください。右側には、各エッジの重み⁠ ⁠ を $w$ $($ $u$ $,$ $v$ $) +$ $h$ $($ $u$ $) -$ $h$ $($ $v$ $)$ に置き換えることによって形成された、重み付けが再設定されたグラフが表示されています。この重み付けが再設定されたグラフでは、すべてのエッジの重みが非負ですが、任意の 2 つのノード間の最短経路は、元のグラフの同じ 2 つのノード間の最短経路と同じエッジのシーケンスを使用します。アルゴリズムは、再重み付けされたグラフ内の 4 つの開始ノードそれぞれに Dijkstra アルゴリズムを適用することで終了します。 $w(u,v)$

正確さ

再重み付けされたグラフでは、ノードのペア $s$ と $t$ 間のすべてのパスに、同じ量 $h (s) - h (t)$ が追加されます。前のステートメントは次のように証明できます。 $p を$ パス $st$ とします。再重み付けされたグラフでのその重み W は次の式で与えられます。

$\left(w(s,p_{1})+h(s)-h(p_{1})\right)+\left(w(p_{1},p_{2})+h(p_{1})-h(p_{2})\right)+...+\left(w(p_{n},t)+h(p_{n})-h(t)\right).$

前の括弧内の式では、はすべてによってキャンセルされます。したがって、 Wについては次の式が残ります。 $+h(p_{i})$ $-h(p_{i})$

$\left(w(s,p_{1})+w(p_{1},p_{2})+\cdots +w(p_{n},t)\right)+h(s)-h(t)$

括弧内の式は、元の重み付けにおける pの重みです。

再重み付けにより、すべてのパス $st$ の重みに同じ量が追加されるため、パスが元の重み付けで最短パスとなるのは、再重み付け後に最短パスとなる場合のみです。qから任意のノードへの最短パスに属するエッジの重みはゼロであるため、qからすべてのノードへの最短パスの長さは、再重み付けされたグラフでゼロになります。ただし、それらは依然として最短パスのままです。したがって、負のエッジは存在できません。エッジuv が再重み付け後に負の重みを持つ場合、 qからuへの長さがゼロのパスはこのエッジと一緒にqからvへの負の長さのパスを形成しますが、これはすべての頂点がqから距離がゼロであるという事実と矛盾します。負のエッジが存在しないことで、ダイクストラのアルゴリズムによって見つかったパスの最適性が保証されます。元のグラフの距離は、再重み付け変換を逆にすることで、再重み付けされたグラフでダイクストラのアルゴリズムによって計算された距離から計算できます。^[1]

分析

ダイクストラ法の実装でフィボナッチヒープを使用するこのアルゴリズムの時間計算量は: アルゴリズムは、アルゴリズムのベルマンフォード段階と、ダイクストラ法の各インスタンス化に時間を使用します。したがって、グラフが疎な場合、合計時間は、同じ問題をで解くフロイド・ワーシャル法よりも速くなります。^[1] $O(|V|^{2}\log |V|+|V||E|)$ $O(|V||E|)$ $O(|V|\log |V|+|E|)$ $|V|$ $O(|V|^{3})$

参考文献

^ abcd コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト; Stein、Clifford (2001)、『アルゴリズム入門』、MIT Press および McGraw-Hill、ISBN 978-0-262-03293-3セクション25.3「スパースグラフに対するジョンソンのアルゴリズム」、636〜640ページ。
^ ab Black, Paul E. (2004)、「ジョンソンのアルゴリズム」、アルゴリズムとデータ構造の辞書、国立標準技術研究所。
^ ジョンソン、ドナルド B. (1977)、「スパースネットワークにおける最短経路の効率的なアルゴリズム」、Journal of the ACM、24 (1): 1–13、doi : 10.1145/321992.321993、S2CID 207678246。
^ Edmonds, J.; Karp, Richard M. (1972)、「ネットワークフロー問題におけるアルゴリズム効率の理論的改善」、Journal of the ACM、19 (2): 248–264、doi :10.1145/321694.321699。
^ Suurballe, JW (1974)、「ネットワーク内の分離パス」、Networks、14 (2): 125–145、doi :10.1002/net.3230040204。

外部リンク

ブースト: 全ペア最短経路

[clrs-1] コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト; Stein、Clifford (2001)、『アルゴリズム入門』、MIT Press および McGraw-Hill、ISBN 978-0-262-03293-3セクション25.3「スパースグラフに対するジョンソンのアルゴリズム」、636〜640ページ。

[black-2] Black, Paul E. (2004)、「ジョンソンのアルゴリズム」、アルゴリズムとデータ構造の辞書、国立標準技術研究所。

[3] ジョンソン、ドナルド B. (1977)、「スパースネットワークにおける最短経路の効率的なアルゴリズム」、Journal of the ACM、24 (1): 1–13、doi : 10.1145/321992.321993、S2CID 207678246。

[4] Edmonds, J.; Karp, Richard M. (1972)、「ネットワークフロー問題におけるアルゴリズム効率の理論的改善」、Journal of the ACM、19 (2): 248–264、doi :10.1145/321694.321699。

[5] Suurballe, JW (1974)、「ネットワーク内の分離パス」、Networks、14 (2): 125–145、doi :10.1002/net.3230040204。