無向グラフに関するKSPAの提案

Question

書き換えが必要な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番目の最短パスを取得するには＆＃8216; k-1＆＃8217; SPTは、各送信元と送信先のペアと＆＃8216; k-1＆＃8217;の間にあります。 1つのSPTからのエッジは、すべての組み合わせに対して同時に削除されます。 明らかに、このアルゴリズムには組み合わせの複雑さがあり、大きなグラフでサーバーを詰まらせます。 Eppsteinのアルゴリズム（ http：//www.ics。 uci.edu/~eppstein/pubs/Epp-SJC-98.pdf ）。しかし、このホワイトペーパーは「有向グラフ」を引用しており、有向グラフのみで機能するという言及はありませんでした。誰かがこのアルゴリズムを無向グラフで使用したかどうかをここで尋ねたかったのですか？

そうでない場合、無向グラフにKSPAを実装するための（時間の複雑さの点で）良いアルゴリズムはありますか？

事前に感謝、

Answer 1

時間の複雑さ：O（K *（E * log（K）+ V * log（V）））

O（K * V）のメモリの複雑さ（入力を保存するための+ O（E））。

次のように修正されたDjikstraを実行します。

• ノードごとに、開始ノードからのルートの現在知られている最高のコストを維持する代わりに。開始ノードからK個の最適なルートを保持します
• ノードの近隣を更新するとき、（ジクストラが行うように）現在既知の最良のパスを改善するかどうかはチェックせず、Kの現在既知の最良パスの最悪を改善するかどうかを確認します。
• ノードの最初のK最適ルートを既に処理した後、K最適ルートを見つける必要はありませんが、K-1のみを残し、別のK-2を残します。それが私がK 'と呼んだものです。
• ノードごとに、現在既知のK '個のパス長の優先度キューを2つ保持します。
  • 1つの優先度キューでは、最短パスが一番上にあります。この優先度キューを使用して、どのK 'が最適かを判断し、通常のジクストラの優先度キューでノードの代表として使用されます。
  • 他の優先度キューでは、最長パスが一番上にあります。これを使用して、候補パスを最悪のK 'パスと比較します。