Znalezienie najkrótszej ścieżki między dwoma węzłami

Biorąc pod uwagę ważony digraf $G=V,E$ i funkcja wagi, $d(u,v)$ , zwykle można użyć algorytmu Dijkstry, aby uzyskać najkrótszą ścieżkę. Interesuje mnie to, jak uzyskać $2^{nd}$ - najkrótsza ścieżka, $3^{rd}$ -krótko i tak dalej.

Pytania:

Czy istnieje skuteczny algorytm do uzyskania i-tej najkrótszej ścieżki między dwoma węzłami na wykresie ważonym?

Czy istnieje skuteczny algorytm pozwalający uzyskać k-najkrótszych ścieżek między dwoma węzłami na wykresie ważonym?

Odpowiedź na jedno z nich jest OK, choć zastanawiam się, czy odpowiedź na drugie pytanie może być wykonana bardziej efektywnie niż $k$ wzywa do odpowiedzi na pierwsze pytanie.

algorithms graphs shortest-path graph-traversal Realz Slaw
źródło

Wyszukiwanie w Google „k najkrótszych ścieżek” ujawnia szereg odniesień opisujących algorytmy tego problemu. Jest też artykuł w Wikipedii na ten temat: en.wikipedia.org/wiki/K_shortest_path_routing

@DW Odpowiedź na krótkie streszczenie?

Raphael

Odpowiedzi:

w $k$ problem najkrótszej ścieżki , który chcemy znaleźć $k$ ścieżka łącząca daną parę wierzchołków o minimalnej całkowitej długości. W Eppstein [1] działa algorytm $O(m+n \log n + k)$ czas znaleźć $k$ najkrótsze ścieżki (pozwalające na cykle) między parą wierzchołków na wykopie. Dzięki technikom papieru można znaleźć wszystkie ścieżki krótsze niż określony próg, w tych samych ramach czasowych. Istnieje obszerna literatura na ten temat, praca Eppsteina zawiera wiele odniesień i dyskusji.

Jeśli nie zgadzasz się na cykle, możesz przyjrzeć się algorytmowi Hershbergera i in. [2]

[1] Eppstein, David. „Znalezienie k najkrótszych ścieżek”. SIAM Journal on computing 28.2 (1998): 652-673. [ CiteSeerX ]

[2] Hershberger, John, Matthew Maxel i Subhash Suri. „Znalezienie k najkrótszych prostych ścieżek: nowy algorytm i jego implementacja”. Transakcje ACM na algorytmach (TALG) 3.4 (2007): 45. [ CiteSeerX ]

Juho
źródło