イェンのアルゴリズム

このアルゴリズムは、最初のk 最短経路を決定するという 2 つの部分に分解できます。${\displaystyle A^{1}}$そして、他のすべてのk最短経路を決定します。コンテナは${\displaystyle A}$k最短経路を保持する一方、コンテナは${\displaystyle B}$潜在的なk最短経路を保持します。${\displaystyle A^{1}}$ソースからシンクまでの最短経路については、効率的な最短経路アルゴリズムであればどれでも使用できます。

見つけるために${\displaystyle A^{k}}$、 どこ${\displaystyle k}$範囲は${\displaystyle 2}$に${\displaystyle K}$アルゴリズムは、からのすべてのパスが${\displaystyle A^{1}}$に${\displaystyle A^{k-1}}$以前に発見された。${\displaystyle k}$反復処理は、すべての偏差を見つけるという2つのプロセスに分けられます。${\displaystyle {A^{k}}_{i}}$そして、最短経路を選択して${\displaystyle A^{k}}$。なお、この反復では、${\displaystyle i}$範囲は${\displaystyle 1}$に${\displaystyle {Q^{k}}_{k}}$。

最初のプロセスはさらに3つの操作に細分化できます。${\displaystyle {R^{k}}_{i}}$発見${\displaystyle {S^{k}}_{i}}$そして、${\displaystyle {A^{k}}_{i}}$容器へ${\displaystyle B}$ルートパス、${\displaystyle {R^{k}}_{i}}$は、サブパスを見つけることによって選択されます。${\displaystyle A^{k-1}}$最初のものに続く${\displaystyle i}$ノード${\displaystyle A^{j}}$、 どこ${\displaystyle j}$範囲は${\displaystyle 1}$に${\displaystyle k-1}$パスが見つかった場合、エッジのコストは${\displaystyle d_{i(i+1)}}$の${\displaystyle A^{j}}$無限大に設定されます。次に、分岐経路、${\displaystyle {S^{k}}_{i}}$は、分岐ノードからノードまでの最短経路を計算することによって求められます。${\displaystyle i}$シンクへ。以前使用されていた縁の除去${\displaystyle (i)}$に${\displaystyle (i+1)}$分岐経路が異なることを保証する。${\displaystyle {A^{k}}_{i}={R^{k}}_{i}+{S^{k}}_{i}}$ルートパスとスパーパスの追加は、${\displaystyle B}$次に、削除されたエッジ、つまりコストが無限大に設定されたエッジは、元の値に戻されます。

2番目のプロセスは、適切な経路を決定します。${\displaystyle A^{k}}$コンテナ内のパスを見つけることによって${\displaystyle B}$最も低いコストで。このパスはコンテナから削除されます。${\displaystyle B}$容器に挿入${\displaystyle A}$そして、アルゴリズムは次の反復処理へと進む。

このアルゴリズムは、 2つのノード間の最短経路を見つけるためにダイクストラ法を使用することを前提としていますが、代わりに任意の最短経路アルゴリズムを使用することも可能です。

function YenKSP(Graph, source, sink, K): // ソースからシンクまでの最短経路を決定します。 A[0] = Dijkstra(Graph, source, sink); // 潜在的な k 番目の最短経路を格納するためのセットを初期化します。 B = []; kを1から Kまで繰り返す: // 分岐ノードは、前の k 最短パスの最初のノードから最後から 2 番目のノードまでの範囲です。 iを0からsize(A[k − 1]) − 2 まで繰り返す:// スパーノードは、前の k 最短パス k − 1 から取得されます。 spurNode = A[k-1].node(i); // 前の k 最短経路の始点から分岐ノードまでのノードのシーケンス。 rootPath = A[k-1].nodes(0, i); Aの各パス pについて: rootPath == p.nodes(0, i): // 同じルート パスを共有する以前の最短パスの一部であるリンクを削除します。 Graphから p.edge(i,i + 1) を削除します。 rootPath内の各ノード rootPathNodeについて、 spurNode を除く:グラフから rootPathNodeを削除します。 // 分岐ノードからシンクまでの分岐パスを計算します。// 分岐パスが見つかったかどうかも確認することを検討します。 spurPath = Dijkstra(グラフ、spurNode、シンク); // パス全体はルートパスとスパーパスで構成されます。 totalPath = rootPath + spurPath; // 潜在的なk最短パスをヒープに追加します。if (totalPath not in B): B.append(totalPath); // グラフから削除されたエッジとノードを元に戻します。グラフに エッジを復元します。 rootPath内のノードをGraphに復元します。B が空の場合: // これは、分岐パスがない場合、または分岐パスが残っていない場合を処理します。// これは、分岐パスが既に使い果たされている場合 (A に追加されている場合)、 // または分岐パスがまったくない場合(ソース頂点とシンク頂点の両方が「行き止まり」に沿っている場合など)に発生する可能性があります。 壊す; // 潜在的なk最短経路をコスト順にソートします。 B.sort(); // 最もコストの低いパスを追加すると、k 最短パスになります。 A[k] = B[0]; // 実際には、最初の要素を削除しているので、shift を使うべきです B.pop(); Aを返す。

この例では、YenのK最短経路アルゴリズムを使用して、次の3つの経路を計算します。${\displaystyle (C)}$に${\displaystyle (H)}$ダイクストラ法は、最適な経路を計算するために使用されます。${\displaystyle (C)}$に${\displaystyle (H)}$それは${\displaystyle (C)-(E)-(F)-(H)}$コスト5で、このパスはコンテナに追加されます。${\displaystyle A}$そして最初のk最短経路となり、${\displaystyle A^{1}}$。

ノード${\displaystyle (C)}$の${\displaystyle A^{1}}$自身をルートパスとする分岐ノードとなり、${\displaystyle {R^{2}}_{1}=(C)}$端、${\displaystyle (C)-(E)}$は、ルートパスとコンテナ内のパスと一致するため削除されます。${\displaystyle A}$ダイクストラ法は分岐経路を計算するために使用される。${\displaystyle {S^{2}}_{1}}$それは${\displaystyle (C)-(D)-(F)-(H)}$費用は8です。${\displaystyle {A^{2}}_{1}={R^{2}}_{1}+{S^{2}}_{1}=(C)-(D)-(F)-(H)}$コンテナに追加されます${\displaystyle B}$潜在的なk最短経路として。

ノード${\displaystyle (E)}$の${\displaystyle A^{1}}$分岐ノードになる${\displaystyle {R^{2}}_{2}=(C)-(E)}$端、${\displaystyle (E)-(F)}$は、ルートパスとコンテナ内のパスと一致するため削除されます。${\displaystyle A}$ダイクストラ法は分岐経路を計算するために使用される。${\displaystyle {S^{2}}_{2}}$それは${\displaystyle (E)-(G)-(H)}$費用は7です。${\displaystyle {A^{2}}_{2}={R^{2}}_{2}+{S^{2}}_{2}=(C)-(E)-(G)-(H)}$コンテナに追加されます${\displaystyle B}$潜在的なk最短経路として。

ノード${\displaystyle (F)}$の${\displaystyle A^{1}}$ルートパスを持つ分岐ノードとなり、${\displaystyle {R^{2}}_{3}=(C)-(E)-(F)}$端、${\displaystyle (F)-(H)}$は、ルートパスとコンテナ内のパスと一致するため削除されます。${\displaystyle A}$ダイクストラ法は分岐経路を計算するために使用される。${\displaystyle {S^{2}}_{3}}$それは${\displaystyle (F)-(G)-(H)}$費用は8です。${\displaystyle {A^{2}}_{3}={R^{2}}_{3}+{S^{2}}_{3}=(C)-(E)-(F)-(G)-(H)}$コンテナに追加されます${\displaystyle B}$潜在的なk最短経路として。

コンテナ内の３つのパスのうち ${\displaystyle B}$、${\displaystyle {A^{2}}_{2}}$に選ばれる${\displaystyle A^{2}}$コストが7と最も低いからです。このプロセスは3番目のk最短経路まで続きます。ただし、この3回目の反復では、分岐経路が存在しないことに注意してください。そして、選択される経路は${\displaystyle A^{3}}$は ${\displaystyle (C)-(D)-(F)-(H)}$。

グラフのエッジを格納するために、最短経路リスト${\displaystyle A}$、そして潜在的な最短経路リスト${\displaystyle B}$、${\displaystyle N^{2}+KN}$メモリ アドレスが必要です。^{[ 2 ]}最悪の場合、グラフ内のすべてのノードはグラフ内の他のすべてのノードへのエッジを持ち、したがって${\displaystyle N^{2}}$住所が必要です。${\displaystyle KN}$住所は両方のリストに必要です${\displaystyle A}$そして${\displaystyle B}$なぜなら、せいぜい${\displaystyle K}$パスは保存され、^{[ 2 ]}各パスには${\displaystyle N}$ノード。

Yenのアルゴリズムの時間計算量は、分岐経路の計算に使用される最短経路アルゴリズムに依存するため、Dijkstraアルゴリズムを仮定する。Dijkstraアルゴリズムの最悪ケースの時間計算量は${\displaystyle O(N^{2})}$しかし、フィボナッチヒープを使用すると、${\displaystyle O(M+N\log N)}$[ ^{3 ]}ここ^で${\displaystyle M}$はグラフのエッジの数です。Yenのアルゴリズムは${\displaystyle Kl}$分岐経路を計算する際にダイクストラ法を呼び出すと、${\displaystyle l}$は分岐経路の長さです。縮約グラフでは、期待値は${\displaystyle l}$は${\displaystyle O(\log N)}$最悪のケースは${\displaystyle N}$時間計算量は${\displaystyle O(KN(M+N\log N))}$[ ^{4 ]​}

ユージン・ローラーは、イェンのアルゴリズムに修正を加え、重複パスを計算しないという方法を提案した。元のアルゴリズムでは重複パスを計算し、重複が見つかった場合は破棄していた。^{[ 6 ]}これらの重複パスは、ルート内のノードの分岐パスを計算することによって生じる。${\displaystyle A^{k}}$。 例えば、${\displaystyle A^{k}}$から逸脱する${\displaystyle A^{k-1}}$あるノードで${\displaystyle (i)}$. 分岐路、${\displaystyle {S^{k}}_{j}}$どこ${\displaystyle j=0,\ldots ,i}$つまり、計算された値は、すでに計算されているため重複になります。${\displaystyle k-1}$反復。したがって、次のスパーパス上のノードのスパーパスのみ${\displaystyle A^{k-1}}$計算する必要がある、つまり${\displaystyle {S^{k}}_{h}}$どこ${\displaystyle h}$範囲は${\displaystyle (i+1)^{k-1}}$に${\displaystyle (Q_{k})^{k-1}}$この操作を実行するには${\displaystyle A^{k}}$ノードを識別するにはレコードが必要です。${\displaystyle A^{k-1}}$から分岐しました${\displaystyle A^{k-2}}$。