Kth最短パス

Question

循環グラフで特定のノードとエッジのセットのKTH最短パスを見つけるプログラミンググラフアルゴリズム（C ++コードは素晴らしい）を書く方法を知っていますか？

たとえば、最短経路（DijkstraまたはBellman Fordが見つけることができます）は、1番目に短いパスと見なされます。今、2番目に短いパスは、最短のパスの後に来る最短経路です。これで、アルゴリズムがKTHの最短パスを見つけてほしい。次のように、ノード、エッジ、エッジのセットの数が与えられます。

ノードの数：5
エッジ数：6
エッジ：
0 1
0 2
1 2
2 3
3 1
1 4
ソースノード：0
宛先ノード：4

「このグラフにはサイクルが含まれていることに注意してください」ありがとう。

Answer 1

使う 均一なコスト検索 アルゴリズム。ウィキペディアが「返品ソリューション」と言っている場合、やめないでください return しかし、そのリストが含まれるまで、結果をいくつかのリストに追加します k パス。 k'リストの要素（1からカウント）は k'最短経路。

「閉じた」/「探索」セットを保持しないでください。そうしないと、このアルゴリズムが適切に機能しません。