11

これらのアルゴリズムがどのように機能するかを正確に理解しようとしていますが、簡単な説明を見つけることができませんでした. 元の論文の説明よりも理解しやすいこれらのアルゴリズムの説明を誰かが提供または指摘してくれれば、非常にありがたいです。ありがとう。

4

1 に答える 1

20

まず最初に、あなたが話していた論文へのリンクを提供させてください。

Eppstein の論文: D. Eppstein、「k 最短経路の検索」、SIAM J. Comput.、vol. 28、いいえ。2、pp.652–673、1999 年 2 月

Yen の論文: JY Yen、「ネットワーク内の K 最短ループレス パスの検索」、Management Science、vol. 17、いいえ。11, pp. 712–716, 1971.

円のアルゴリズムの説明は次のとおりです。

Yen のアルゴリズムは 2 つのリスト、つまりリスト A (送信元から送信先までの永続的な最短パス - 時系列順) とリスト B (暫定/候補の最短パス) を使用します。最初に、適切な最短パス アルゴリズム (Dijkstra など) を使用して、ソースから宛先への最初の最短パスを見つける必要があります。次に、Yen は、k 番目の最短パスが (k-1) 番目の最短パスのエッジとサブパス (ソースからルート内の任意の中間ノードへのパス) を共有する可能性があるという考えを利用します。次に、(k-1) 番目の最短パスを取り、ルート内の各ノードを順に到達不能にする必要があります。つまり、ルート内のノードに向かう特定のエッジをこすり落とします。ノードが到達不能になったら、前のノードから宛先までの最短パスを見つけます。次に、共通のサブパス (送信元から到達不能ノードの前のノードまで) を追加して作成された新しいルートがあり、前のノードから宛先までの新しい最短パスが追加されます。このルートは、以前にリスト A またはリスト B に表示されていなければ、リスト B に追加されます。ルート内のすべてのノードに対してこれを繰り返した後、リスト B で最短ルートを見つけ、それをリスト A に移動する必要があります。このプロセスを K の数だけ繰り返す必要があります。

このアルゴリズムの計算量は O(kn^3) です。詳細については、論文をお読みください。

アルゴリズムは次のとおりです。

G = Adjacent Matrix of the Network
Initialize:
A_1 = shortest-path from source to destination
Glocal ← Local copy of G
for k = 2 → K do
 for i = 1 → [len(A_(k−1) ) − 1] do
  Current Node ← A_(k−1) [i]
  Ri ← Sub-path (root) from source till current node in A_(k−1)
  for j = 1 → k − 1 do
   Rj ← Sub-path (root) from source till current node in A_j
   if Ri == Rj then
    Next Node ← Aj [i+1]
    Glocal(Current Node, Next Node) ← infinity
    Current Node ← unreachable
   end if
  end for
  Si ← Shortest-path from current node till destination
  Bi ← Ri + Si
 end for 
 A_k ← Shortest-path amongst all paths in B
 Restore original graph: Glocal ← Local copy of G
end for

残念ながら、Yen のアルゴリズムが私の問題に最適だったので、Eppstein のアルゴリズムは使用していません。

お役に立てれば。乾杯。

=====

編集：

ウィキペディアのエントリも参照してください。いい例があります。

=====

編集：

C でいくつかの実装を見つけました。リンクは次のとおりです。

Eppstein の実装と Eppstein のLoading Graph。

興味のある方は、怠惰なバージョンの Eppstein があります。リンクは次のとおりです。

ヒメネスとマルザルによる怠惰なエップスタイン

=====

編集：

ちょうど別のリンク. これにはいくつかの実装 (C/C++) が含まれています。

=====

編集：

エプスタインのアルゴリズムの良い説明を見つけました。

于 2012-12-26T00:43:39.273 に答える