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

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

クラス	全ペア最短経路問題（重み付きグラフの場合）
データ構造	グラフ
最悪の場合の パフォーマンス	${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$

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

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

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

1. まず、新しいノード qがグラフに追加され、ゼロ重みエッジによって他の各ノードに接続されます。
2. 次に、ベルマン・フォードアルゴリズムを使用して、新しい頂点qから始めて、各頂点vについてqからvへのパスの最小重みh ( v )を見つけます。このステップで負のサイクルが検出されると、アルゴリズムは終了します。
3. 次に、ベルマンフォードアルゴリズムによって計算された値を使用して、元のグラフのエッジの重みが再調整されます。つまり、長さ⁠ ⁠ を持つuからvへのエッジに、新しい長さw ( u , v ) + h ( u ) − h ( v )が与えられます。${\displaystyle w(u,v)}$
4. 最後に、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 アルゴリズムを適用することで終了します。 ${\displaystyle w(u,v)}$

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

$${\displaystyle \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については次の式が残ります。 ${\displaystyle +h(p_{i})}$${\displaystyle -h(p_{i})}$

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

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

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

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

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