5

書き直す必要がある KSPA のカスタム実装があります。現在の実装では、修正されたダイクストラのアルゴリズムが使用されています。その疑似コードは、以下で大まかに説明されています。これは一般に、エッジ削除戦略を使用した KSPA として知られていると思います。（私はグラフ理論の初心者です）。

Step:-1.  Calculate the shortest path between any given pair of nodes using the Dijkstra algorithm. k = 0 here.
Step:-2.   Set k = 1
Step:-3.   Extract all the edges from all the ‘k-1’ shortest path trees. Add the same to a linked list Edge_List.
Step:-4.  Create a combination of ‘k’ edges from Edge_List to be deleted at once such that each edge belongs to a different SPT (Shortest Path Tree). This can be done by inspecting the ‘k’ value for each edge of the combination considered. The ‘k’ value has to be different for each of the edge of the chosen combination.
Step:-5.   Delete the combination of edges chosen in the above step temporarily from the graph in memory.
Step:-6.   Re-run Dijkstra for the same pair of nodes as in Step:-1.
Step:-7.   Add the resulting path into a temporary list of paths. Paths_List.
Step:-8.   Restore the deleted edges back into the graph.
Step:-9.   Go to Step:-4 to get another combination of edges for deletion until all unique combinations are exhausted. This is nothing but choosing ‘r’ edges at a time among ‘n’ edges => nCr.
Step:-10. The ‘k+1’ th shortest path is = Minimum(Paths_List).
Step:-11. k = k + 1 Go to Step:-3, until k < N.
Step:-12. STOP

アルゴリズムを理解しているように、k 番目の最短パスを取得するには、各ソースと宛先のペアの間に「k-1」SPT が見つかり、1 つの SPT からそれぞれ「k-1」エッジがすべての組み合わせで同時に削除されます。明らかに、このアルゴリズムには組み合わせの複雑さがあり、大きなグラフでサーバーを詰まらせます。人々はエプスタインのアルゴリズムを提案してくれました ( http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf )。しかし、このホワイト ペーパーでは「ダイグラフ」について言及していますが、それがダイグラフに対してのみ機能するという記述は見当たりませんでした。無向グラフでこのアルゴリズムを使用したことがある人はいますか?

そうでない場合、無向グラフに KSPA を実装するための (時間の複雑さに関して) 優れたアルゴリズムはありますか?

前もって感謝します、

4

1 に答える 1

5

時間計算量: O(K*(E*log(K)+V*log(V)))

O(K*V) のメモリの複雑さ (入力を格納するための +O(E))。

次のように、修正されたジクストラを実行します。

  • ノードごとに、現在知られている最適なルート コストを start-node から保持する代わりに。開始ノードから最適な K ルートを保持します
  • ノードの隣接ノードを更新するとき、現在知られている最良のパスを改善するかどうかはチェックしません (Djikstra のように)。K' の現在知られている最良のパスのうち最悪のものを改善するかどうかをチェックします。
  • ノードの K 個の最適なルートの最初の処理を既に処理した後、K 個の最適なルートを見つける必要はありませんが、残りは K-1 のみで、次は K-2 です。それが私がK'と呼んだものです。
  • ノードごとに、現在知られている K' 個の最適なパス長に対して 2 つの優先キューを保持します。
    • 1 つのプライオリティ キューでは、最短パスが一番上にあります。このプライオリティ キューを使用して、どの K' が最適であり、ノードの代表として通常の Djikstra のプライオリティ キューで使用されるかを決定します。
    • 他のプライオリティ キューでは、最長のパスが一番上にあります。これを使用して、候補パスを最悪の K' パスと比較します。
于 2009-08-25T08:50:05.123 に答える