Finden des k-kürzesten Pfades zwischen zwei Knoten

Bei einem gewichteten Digraphen und einer Gewichtsfunktion d ( u , v ) kann man normalerweise den Dijkstra-Algorithmus verwenden, um den kürzesten Weg zu erhalten. Was mich interessiert, ist, wie man den 2 n d- kürzesten Pfad, den 3 r d- kürzesten Weg und so weiter erhält.$G=V,E$$d(u,v)$$2^{nd}$$3^{rd}$

Fragen:

Gibt es einen effizienten Algorithmus, um den i-ten kürzesten Pfad zwischen zwei Knoten in einem gewichteten Graphen zu ermitteln?

Gibt es einen effizienten Algorithmus, um die k-kürzesten Pfade zwischen zwei Knoten in einem gewichteten Graphen zu erhalten?

Eine Antwort auf eine der beiden Fragen ist in Ordnung, obwohl ich mich frage, ob eine Antwort auf die zweite Frage effizienter erfolgen kann als Aufrufe auf eine Antwort auf die erste Frage.$k$

$k$$k$$O(m+n \log n + k)$$k$

Wenn Sie Zyklen nicht zulassen, sollten Sie sich den Algorithmus von Hershberger et al. [2].

[1] Eppstein, David. "Die k kürzesten Wege finden." SIAM Journal on Computing 28.2 (1998): 652 & ndash; 673. [ CiteSeerX ]

[2] Hershberger, John, Matthew Maxel und Subhash Suri. "Die k kürzesten einfachen Wege finden: Ein neuer Algorithmus und seine Implementierung." ACM-Transaktionen zu Algorithmen (TALG) 3.4 (2007): 45. [ CiteSeerX ]