KTH kürzester Weg

Question

Weiß jemand, wie ich einen Programmiergraph-Algorithmus (C ++-Code großartig wäre) schreiben kann, der den k-ten kürzesten Pfad für einen bestimmten Satz von Knoten und Kanten in einem zyklischen Diagramm findet?

Zum Beispiel wird der kürzeste Weg (der von Dijkstra oder Bellman Ford gefunden werden kann) als der 1. kürzeste Weg. Jetzt ist der zweitkürzeste Weg der kürzeste, der nach dem ersten kürzesten Weg kommt. Jetzt möchte ich, dass der Algorithmus den kürzesten KTH -Weg findet. Sie erhalten die Anzahl der Knoten, Kanten und die Menge der Kanten wie folgt:

Anzahl der Knoten: 5
Anzahl der Kanten: 6
Kanten:
0 1
0 2
1 2
2 3
3 1
1 4
Quellknoten: 0
Zielknoten: 4

"Beachten Sie, dass dieses Diagramm einen Zyklus enthält" Danke.

Answer 1

Verwenden ein Einheitliche Kostensuche Algorithmus. Wo die Wikipedia "Rückkehrlösung" sagt, kündigen Sie nicht und return Fügen Sie das Ergebnis jedoch einer Liste an, bis diese Liste enthält k Wege. Das kDas Element der Liste (Zählung von 1) ist das k'Th der kürzeste Weg.

Halten Sie kein "geschlossen"/"erkundet", oder dieser Algorithmus funktioniert nicht ordnungsgemäß.