シュールバルのアルゴリズム

理論計算機科学とネットワークルーティングにおいて、スルバーレのアルゴリズムは、非負の重み付き有向グラフで2つの互いに素なパスを見つけるアルゴリズムであり、両方のパスが同じ頂点のペアを接続し、合計の長さが最小になるようにします。^[1]このアルゴリズムは、John W. Suurballeによって考案され、1974年に発表されました。 ^[2]スルバーレのアルゴリズムの主なアイデアは、ダイクストラのアルゴリズムを使用して1つのパスを見つけ、グラフのエッジの重みを変更してから、ダイクストラのアルゴリズムをもう一度実行することです。アルゴリズムの出力は、これら2つのパスを結合し、パスが反対方向に通過するエッジを破棄し、残りのエッジを使用して2つのパスを形成し、出力として返すことによって形成されます。重みの変更は、ジョンソンのアルゴリズムの重みの変更に似ており、重みの非負性を維持しながら、ダイクストラのアルゴリズムの 2 番目のインスタンスが正しい 2 番目のパスを見つけることができるようにします。

最小の重みを持つ 2 つの分離したパスを見つける問題は、最小コスト フロー問題の特殊なケースと見なすことができます。この場合、「フロー」の単位が 2 つあり、ノードには単位の「容量」があります。Suurballe のアルゴリズムも、最小コスト フロー アルゴリズムの特殊なケースと見なすことができます。このアルゴリズムは、最短の増加パスに沿って、可能な限り最大のフロー量を繰り返しプッシュします。Suurballe のアルゴリズムによって最初に見つかったパスは、初期 (ゼロ) フローの最短の増加パスであり、Suurballe のアルゴリズムによって見つかった 2 番目のパスは、最初のパスに沿って 1 単位のフローを押した後に残った残余グラフの最短の増加パスです。

G を頂点集合Vと辺集合 Eを持つ重み付き有向グラフとします (図 A)。 sをG内の指定されたソース頂点 、 tを指定されたデスティネーション頂点とします。 E内の 頂点 uから頂点 vへの各辺( u , v ) のコストは非負の w ( u , v )とします。

頂点sを根とする最短経路木において、頂点sから頂点uへの最短経路のコストをd( s , u )と定義する（図C）。

注: ノードと頂点は、同じ意味で使用されることがよくあります。

Suurballe のアルゴリズムは、次の手順を実行します。

1. ダイクストラのアルゴリズムを実行して、ノードsをルートとする最短経路ツリーTを見つけます (図 C)。このツリーには、すべての頂点uについて、sからuへの最短経路が含まれます。P _1をsからtへの最短コスト経路とします (図 B)。 T内のエッジはツリー エッジと呼ばれ、残りのエッジ (図 C にないエッジ) は非ツリー エッジと呼ばれます。
2. グラフの各辺のコストを変更するには、すべての辺( u、v )のコストw ( u、v )をw′ ( u、v ) = w ( u、v ) − d( s、v ) + d( s、u )に置き換えます。結果として得られる変更されたコスト関数によれば、すべてのツリー エッジのコストは 0 で、非ツリー エッジのコストは非負になります。たとえば、u =B、v =Eの場合、w′ ( u、v ) = w (B、E) − d(A、E) + d(A、B) = 2 − 3 + 1 = 0 u =E、v =Bの場合、w′ ( u、v ) = w (E、B) − d(A、B) + d(A、E) = 2 − 1 + 3 = 4
   
   
3. パスP _1上のGのsに向かうエッジを削除し、パスP ₁に沿った長さゼロのエッジの方向を反転することで、 Gから形成された残差グラフG _{t を}作成します(図 D)。
4. ダイクストラのアルゴリズムを実行して、残差グラフG _t内の最短パスP _{2 を}見つけます(図 E)。
5. 両方のパスからP ₂の反転エッジを破棄します。P ₁とP ₂の残りのエッジは、sに 2 つの出力エッジ、 tに 2 つの入力エッジ、残りの各頂点に 1 つの入力エッジと 1 つの出力エッジを持つサブグラフを形成します。したがって、このサブグラフは、 sからtへの 2 つのエッジが互いに素なパスと、場合によってはいくつかの追加の (長さゼロの) サイクルで構成されます。サブグラフから 2 つの互いに素なパスを返します。

次の例は、Suurballe のアルゴリズムがAからFへの最短の分離パスのペアをどのように見つけるかを示しています。

図A は重み付きグラフGを示しています。

図BはAからF（A – B – D – F ）への最短経路P _1を計算します。

図Cは、Aをルートとする最短経路木Tと、Aから各頂点( u )までの計算された距離を示しています。

図Dは、各エッジのコストが更新され、パスP ₁のエッジが反転された残差グラフG _{t を}示しています。

図Eは残差グラフGt ( A – C – D – B – E – F ₎のパスP2_を計算します。

図F はパスP ₁とパスP _{2 の}両方を示しています。

図G は、パスP ₁とP ₂のエッジを結合し、両方のパス間の共通の逆エッジ ( B – D ) を破棄することで、最短の非結合パスのペアを見つけます。その結果、2 つの最短の非結合パスのペア ( A – B – E – F ) と ( A – C – D – F ) が得られます。

修正された重みシステムにおけるsからtへの任意のパスの重みは、元のグラフの重みからd( s , t )を引いた値に等しくなります。したがって、修正された重みによる最短の 2 つの分離パスは、重みは異なりますが、元のグラフの最短の 2 つのパスと同じパスになります。

Suurballe のアルゴリズムは、 sからtまでの総フロー量が 2 である最小コスト フローを見つけるための、連続最短経路法の特殊なケースと見なすことができます。重みの変更は、この方法で見つかったパスのシーケンスには影響せず、重みのみに影響します。したがって、アルゴリズムの正確さは、連続最短経路法の正確さから得られます。

このアルゴリズムでは、ダイクストラのアルゴリズムを 2 回反復する必要があります。フィボナッチ ヒープを使用すると、両方の反復を で実行できます。ここで、と はそれぞれ頂点と辺の数です。したがって、同じ時間制限が Suurballe のアルゴリズムに適用されます。 ${\displaystyle O(|E|+|V|\log |V|)}$${\displaystyle |V|}$${\displaystyle |E|}$

上で説明した Suurballe のアルゴリズムのバージョンは、辺が互いに重ならないが頂点を共有している可能性のあるパスを見つけます。同じアルゴリズムを使用して、各頂点を隣接する頂点のペアに置き換え、1 つは元の頂点のすべての入力隣接 u-inを持ち、もう 1 つはすべての出力隣接 u-outを持つようにすることで、頂点が互いに重ならないパスを見つけることもできます。この修正されたグラフの 2 つの辺が互いに重ならないパスは、元のグラフの 2 つの頂点が互いに重ならないパスに必然的に対応し、その逆も同様です。そのため、修正されたグラフに Suurballe のアルゴリズムを適用すると、元のグラフに 2 つの頂点が互いに重ならないパスが構築されます。Suurballe の 1974 年の元のアルゴリズムは、問題の頂点が互いに重ならないバージョン用でしたが、1984 年に Suurballe と Tarjan によって辺が互いに重ならないバージョンに拡張されました。^[3]

グラフG _t内の各頂点tまでの距離を同時に計算する Dijkstra アルゴリズムの修正バージョンを使用することで、特定のソース頂点sからグラフ内の他のすべての頂点までの最短パスのペアの合計長さを、Dijkstra アルゴリズムの単一インスタンスに比例する時間で見つけることもできます。

注: 分割の結果生じた隣接する頂点のペアは、入ってくる頂点から出ていく頂点へのゼロコストの単方向エッジによって接続されます。ソース頂点はs-outになり、宛先頂点はt-inになります。

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