書き直す必要がある 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 を実装するための (時間の複雑さに関して) 優れたアルゴリズムはありますか?
前もって感謝します、