エッジ分離最短ペアアルゴリズム

辺素最短ペアアルゴリズムは、コンピュータネットワークルーティングのアルゴリズムです。^{[1]このアルゴリズムは、与えられた}頂点のペア間の辺素パスの最短ペアを生成するために使用されます。無向グラフG(V, E)の場合、次のように表されます。

1. 与えられた頂点のペアに対して最短経路アルゴリズムを実行する
2. 最短経路の各辺（反対方向の弧2つに相当）を、ソース頂点に向かう単一の弧に置き換えます。
3. 上記の各弧の長さを負にする
4. 最短経路アルゴリズムを実行します（注：アルゴリズムは負のコストを受け入れる必要があります）
5. 見つかった 2 つのパスの重なり合うエッジを消去し、最初の最短パス上の残りの円弧の方向を反転して、その上の各円弧が目的の頂点に向かうようにします。目的のパスのペアが作成されます。

グラフ内のどこにでも存在する負のアーク（負のサイクルは存在しない）に有効な汎用のフォードの最短経路アルゴリズム^{[2] [3]}の代わりに、Bhandari ^[4]は2つの異なるアルゴリズムを提供しており、そのどちらもステップ4で使用できます。 1つのアルゴリズムは、従来のダイクストラのアルゴリズムをわずかに修正したもので、もう1つは幅優先探索（BFS）アルゴリズムと呼ばれ、ムーアのアルゴリズムの変形です。^{[5] [6]}負のアークは最初の最短経路上にのみ存在するため、変換されたグラフ（ステップ2と3）には負のサイクルは発生しません。 非負のグラフでは、修正されたダイクストラアルゴリズムは従来のダイクストラアルゴリズムに簡略化されるため、上記のアルゴリズムのステップ1で使用できます（同様に、BFSアルゴリズムでも使用できます）。

出典: ^{[4] [7]}

G = (V, E) d(i) – 始点頂点 A からの頂点 i (i∈V) の距離。頂点 A から頂点 i までの可能な経路の弧の合計です。d(A)=0 であることに注意してください。P(i) – 同じ経路上の頂点 i の前の頂点。Z – 終点頂点

ステップ1。

d(A) = 0から始め、
d(i) = l (Ai)、i∈Γ Aの場合; Γ i ≡ 頂点iの隣接頂点の集合、l(ij) = 頂点iから頂点jまでの弧の長さ。
      
         = ∞、それ以外の場合。       
S = V-{A} を割り当てます。ここで、V は指定されたグラフ内の頂点の集合です。
P(i) = A, ∀i∈Sを代入します。

ステップ2。

a) d(j) = min d(i), i∈Sとなるj∈Sを見つけます。
b) S = S – {j}と設定します。
c) j = Z (目的の頂点) の場合は終了、それ以外の場合はステップ 3 に進みます。

ステップ3。

∀i∈Γ j、もし d(j) + l(ji) < d(i) ならば、
a) d(i) = d(j) + l(ji)、P(i) = jと設定します。
b) S = S ∪{i}
ステップ2に進みます。

エッジ分離最短ペア アルゴリズムの主な手順を以下に示します。

図Aは、辺の重みを持つ無向グラフG(V, E)を示しています。

図 B は、A から Z までの計算された最短経路 ABCZ (太線) を示しています。

図 C は、最短経路の弧の反転とその負の重みを示しています。

図 D は、図 C の新しい変換されたグラフで決定された A から Z への最短パス ADCBZ を示しています (これは、このような負の弧に有効な修正ダイクストラ アルゴリズム (または BFS アルゴリズム) を使用して決定されます。このような変換されたグラフには、負のサイクルは存在しません)。

図 E は、元のグラフで決定された最短パス ADCBZ を示しています。

図 F は、パス ABCZ と ADCBZ に共通するエッジ BC を消去し、残りのエッジを適切にグループ化した後に見つかった、エッジが互いに素なパスの最短ペア (ABZ、ADCZ) を示しています。

非負グラフでは、修正ダイクストラ法は従来のダイクストラ法と同じように機能します。頂点の次数が O(d) (d<|V|) であるグラフでは、効率は O(d|V|) で、最悪の場合でも従来のダイクストラ法の場合と同様に O(|V| ² ) になります。

エッジ分離最短ペア アルゴリズムの変換されたグラフには負の弧が含まれていますが、修正ダイクストラ アルゴリズムのステップ 2a で以前に「恒久的に」ラベル付けされた特定の頂点は、ステップ 3a で再訪され、再ラベル付けされ、頂点セット S に挿入されることがあります (ステップ 3b)。このような変換されたグラフでの修正ダイクストラの効率は O(d ² |V|) となり、最悪の場合でも O(|V| ³ ) になります。実用的な関心のあるグラフのほとんどは通常スパースであり、頂点の次数は O(1) です。この場合、変換されたグラフに適用された修正ダイクストラ アルゴリズムの効率は O(|V|) (または同等に O(|E|)) になります。すると、辺素最短ペア アルゴリズムの効率は、Suurballe のアルゴリズムと同等になります。Suurballeのアルゴリズムは、負のコスト アークを回避するためにグラフの重み付けを変更する追加のグラフ変換により、一般に O(|V| ² )となり、ダイクストラ アルゴリズムを両方の最短経路ステップで使用できるようになります。重み付けを変更するには、ソース頂点をルートとする最短経路ツリー全体を構築する必要があります。この追加のグラフ変換を回避し、代わりに修正されたダイクストラ アルゴリズムを使用することで、Bhandari のアプローチは、少なくともスパース グラフに対して効率をあまり犠牲にすることなく、辺素最短ペア アルゴリズムの簡略化されたバージョンを生み出します。結果として得られる単純な形式は、K (>2) の素パス アルゴリズムや、完全な素性が存在しない部分的な素パスなどのそのバリエーションへの簡単な拡張^{[8] [9]}や、より複雑な現実のネットワークで実践的なネットワーク専門家が遭遇する制約のあるグラフにも適しています。

上記の辺分離最短パス アルゴリズムの頂点分離バージョンは、アルゴリズムのステップ 3 の最初の最短パスの各頂点 (ソース頂点と宛先頂点を除く) を分割し、分割された頂点ペアをゼロ重みアーク (ソース頂点に向かう方向) で接続し、入射エッジを 2 つの反対方向のアーク (1 つは分割ペアの頂点 (ソース頂点に近い方) に入射し、もう 1 つは他の頂点から放射されるアーク) に置き換えることによって得られます。K (>2) バージョンも同様に得られます。たとえば、最短の辺分離パス ペアの頂点 (ソース頂点と宛先頂点を除く) が分割され、各分割ペアの頂点がゼロ重みアークで互いに接続され、外部エッジも同様の方法で接続されます^[8][9]。無向グラフ用に提示されたアルゴリズムは有向グラフにも拡張され、頂点と辺 (または弧) のグラフとしてモデル化できるあらゆる問題 (あらゆる技術分野) に一般的に適用されます。