Algorytm Yena

Algorytm Yena oblicza z jednego źródła K - najkrótsze ścieżki bez pętli dla grafu z nieujemnym kosztem krawędzi . Algorytm został opublikowany przez Jin Y. Yen w 1971 roku i wykorzystuje dowolny algorytm najkrótszej ścieżki , aby znaleźć najlepszą ścieżkę, a następnie przechodzi do znalezienia K - 1 odchyleń najlepszej ścieżki.

Algorytm

Terminologia i notacja

Notacja	Opis
${\ displaystyle N}$	Rozmiar wykresu, czyli liczba węzłów w sieci.
${\ Displaystyle (i)}$	Ja ${\ displaystyle i ^ {th}}$$\ displaystyle N}$ wykresu, gdzie $do$ się od ${\ displaystyle 1}$ N . $.$ to, że $jest$ wykresu i węzłem
${\ Displaystyle d_ {ij}}$	Koszt przewagi między i $Displaystyle (i$ ≠ $} i ($$) {\ Displaystyle ($ jot ) ${\ Displaystyle d_ {ij} \ geq 0}$ .
${\ Displaystyle A ^ {k}}$	K $th}}$ { najkrótsza ścieżka od do ${\ Displaystyle ($$N)}$${\ Displaystyle k}$ się od $} displaystyle 1}$ do ${\ displaystyle K}$ . Wtedy $N)}$${\ Displaystyle A ^ {k} = (1) - (2 ^ {k}) - (3 ^ {k}) - \ cdots - ({Q_ {k} } ^ {k}) -$$\ Displaystyle$ , gdzie jest drugim węzłem i $(2 ^ {k})$${\ Displaystyle (3 ^ {k})}$ jest trzecim węzłem ${\ Displaystyle k ^ {th}}$ najkrótsza ścieżka i tak dalej.
${\ Displaystyle {A ^ {k}} _ {i}}$	Ścieżka odchylenia od w węźle $,$$(i)}$$\ Displaystyle A ^ {$ gdzie się od do ${\ Displaystyle Q_ {k}}$$-1}}$ . Zauważ $,$ że maksymalna wartość to , która jest węzłem tuż przed zlewem w . $k$$}$ najkrótsza droga. $,$ że ścieżka odchylenia nie może odbiegać od ścieżki w zlewie Ścieżki i $_$$tą$ samą $,$ _ ${\ Displaystyle (i) ^ {k} - (i + 1) ^ {k}}$ krawędź różni się od dowolnej ścieżki w $displaystyle$ gdzie waha się od $do$$\ displaystyle 1}$ k $k-1$ .
${\ Displaystyle {R ^ {k}} _ {i}}$	Ścieżka główna ${\ Displaystyle {A ^ {k}} _ {i}}$ , która wynika z tego, że ${\ Displaystyle A ^ {k-1}}$ aż do ${\ displaystyle i_ { th}}$ węzeł ZA $Displaystyle A ^ {k-1}}$ .
${\ Displaystyle {S ^ {k}} _ {i}}$	Ścieżka ostrogi , która zaczyna $}}_{i}}$ w $}$ węzła ZA ${$$^ {$ i kończy się przy zlewie.

Opis

Algorytm można podzielić na dwie części, określając pierwszą $k$ najkrótszą ścieżkę , a następnie wszystkie inne k - najkrótsze ścieżki . Zakłada się, że pojemnik $k$ zawierał - $najkrótszą$ ścieżkę, podczas gdy pojemnik będzie zawierał potencjalne k - ścieżki. Aby określić $_$ _ od źródła do ujścia można zastosować dowolny efektywny algorytm najkrótszej ścieżki .

$A ^ {1}}$ znaleźć $,$ gdzie się $od do ,$$zakłada$ , że ​​wszystkie ścieżki z k $}$$K$ do ${\ Displaystyle A ^ {k-1}}$ zostały znalezione wcześniej. Iterację można podzielić na dwa procesy, znajdując $wszystkie$${\ displaystyle {A ^ {k}} _ {i}}$ i wybierając ścieżkę o minimalnej długości, aby stać się ${\ displaystyle A ^ {k}}$ . $waha$$się$ w tej iteracji od $1}$ displaystyle do

Pierwszy proces można dalej podzielić na trzy operacje, wybierając ${\ Displaystyle {R ^ {k}} _ {i}}$ , znajdując ${\ Displaystyle {S ^ {k}} _ {i} }$ , a następnie dodanie do kontenera ${\ displaystyle {A ^ {k$$} _ {i}}$ . Ścieżka główna $1}}$ znalezienie ścieżki podrzędnej w $1 {\$ który następuje po pierwszych węzłach ${\ Displaystyle$$^ {j}}$ gdzie $do$ się od ${\ Displaystyle 1}$ k $\ Displaystyle k-1}$ . $Następnie$ , $jeśli$ ścieżka koszt Dalej ścieżka ostrogi, ${\ displaystyle {S ^ {k}} _ {i}}$ , znajduje się przez obliczenie najkrótszej ścieżki od węzła ostrogi, $,$ do zlewu. Usunięcie wcześniej używanych krawędzi z ${\ Displaystyle (i)}$ do ${\ Displaystyle (i + 1)}$ , że ​​ścieżka ostrogi jest inna. ${\ Displaystyle {A ^ {k}} _ {i} = {R ^ {k}} _ {i} + {S ^ {k}} _ {i}}, dodanie ścieżki korzenia i ścieżki$ ostrogi , dodaje się do ${\ displaystyle B}$ . Następnie krawędzie, które zostały usunięte, czyli których koszt był ustawiony na nieskończoność, są przywracane do wartości początkowych.

Drugi proces określa odpowiednią ścieżkę dla, $znajdując$$w$ kontenerze koszcie. $Ta ścieżka jest usuwana z kontenera i wstawiana do kontenera,$ algorytm $następnej$ do iteracji.

Pseudo kod

Algorytm zakłada, że ​​algorytm Dijkstry służy do znalezienia najkrótszej ścieżki między dwoma węzłami, ale w jego miejsce można zastosować dowolny algorytm najkrótszej ścieżki.

         0  function  YenKSP(Graph, source, sink, K):  // Określ najkrótszą ścieżkę od źródła do ujścia.  A[0] = Dijkstra(wykres, źródło, ujście);  // Zainicjuj zestaw do przechowywania potencjalnej k-tej najkrótszej ścieżki.  B = [];  for  k  od  1  do  K:  // Węzeł ostrogi rozciąga się od pierwszego węzła do przedostatniego węzła w poprzedniej k-najkrótszej ścieżce.  dla  i  od  do  size(A[k − 1]) − 2:  // Węzeł Spur jest pobierany z poprzedniej k-najkrótszej ścieżki, k − 1.  spurNode = A[k-1].node(i);  // Sekwencja węzłów od źródła do węzła ostrogi poprzedniej k-najkrótszej ścieżki.  rootPath = A[k-1].nodes(0, i);  dla każdej  ścieżki p  w  A:  if  rootPath == p.nodes(0, i):  // Usuń łącza, które są częścią poprzednich najkrótszych ścieżek, które mają tę samą ścieżkę główną.  usuń p.edge(i,i + 1)  z 
            
             Wykres;  dla każdego  węzła rootPathNode  w  rootPath z wyjątkiem spurNode: usuń rootPathNode  z  Graph;  // Oblicz ścieżkę ostrogi od węzła ostrogi do ujścia.  // Rozważ także sprawdzenie, czy znaleziono ścieżkę spurPath  ostroPath = Dijkstra(Graph, spurNode, sink);  // Cała ścieżka składa się ze ścieżki głównej i ścieżki ostrogi.  totalPath = rootPath + spurPath;  // Dodaj potencjalną k-najkrótszą ścieżkę do sterty.  Jeśli 
            
             (totalPath nie w B): B.append(totalPath);  // Dodaj z powrotem krawędzie i węzły, które zostały usunięte z grafu.  przywróć krawędzie  do  wykresu; przywróć węzły w rootPath   do  Graph;  if  B jest puste:  // Obsługuje to przypadek, gdy nie ma ścieżek ostrogowych lub nie ma już ścieżek ostrogowych.  // Może się to zdarzyć, jeśli ścieżki ostrogowe zostały już wyczerpane (dodane do A),  // lub w ogóle nie ma ścieżek ostrogowych - na przykład gdy zarówno wierzchołki źródłowe, jak i ujścia 
             // leżeć w „ślepym zaułku”.  przerwa;  // Sortowanie potencjalnych k-najkrótszych ścieżek według kosztu.  sortowanie B.();  // Dodanie ścieżki o najniższym koszcie staje się k-najkrótszą ścieżką.  A[k] = B[0];  // Właściwie powinniśmy raczej użyć przesunięcia, ponieważ usuwamy pierwszy element  B.pop();  powrót  A; 

Przykład

K - najkrótszej ścieżki jena do obliczenia trzech ścieżek od ${\ displaystyle (C)}$ do ${\ displaystyle (H)}$ . Algorytm Dijkstry służy do obliczenia najlepszej ścieżki od ${\ Displaystyle (C)}$ do ${\ Displaystyle (H)}$ , czyli ${\ Displaystyle (C) - (E) - (F) - (H)}$ z kosztem 5. Ta ścieżka jest dołączana do kontenera $najkrótszą$ staje się pierwszą k - ścieżką, ${\ Displaystyle A ^ {1}}$ .

Węzeł $)}$ do $}_{1}=(C)}$ staje się węzłem bocznym z własną ścieżką korzeniową, $^$${\ Displaystyle {R$ . Krawędź $jest$$, ponieważ$ ścieżką główną Algorytm Dijkstry służy do obliczenia ścieżki ostrogi $czyli$ ( $Displaystyle (C)$ , z kosztem 8. ${\ Displaystyle {A ^ {2}} _ {1} = {R ^ {2}} _ {1} + {S ^ {2}} _ {1} = (C) - ( D) - (F) - (H)}$ jest dodawane do pojemnika $najkrótsza$ potencjalna k - ścieżka.

Węzeł $E)}$${R ^ {2}} _ {2}=(C)-(E)}$ staje się węzłem bocznym z $Displaystyle$ - . Krawędź $jest$$,$ ponieważ pokrywa się główną Algorytm Dijkstry służy do obliczania ścieżki ostrogi $,$$Displaystyle (E) - ($ ( , z kosztem 7. ${\ Displaystyle {A ^ {2}} _ {2} = {R ^ {2}} _ {2} + {S ^ {2}} _ {2} = (C) - (E) - (G) - (H)}$ jest dodawane do kontenera $najkrótsza$ potencjalna k - ścieżka.

Węzeł $)} staje$$Displaystyle ($$\ Displaystyle {R^{2}}_{3}=(C)-(E)-(F)}$ węzłem bocznym ze ścieżką główną, do . Krawędź jest usuwana, ponieważ pokrywa się ze ścieżką główną i ścieżką w kontenerze ( $\ Displaystyle (F) - (H)}$${\ displaystyle A}$ . Algorytm Dijkstry służy do obliczania ścieżki ostrogi $- ($$czyli$ sol , z kosztem 8. ${\ Displaystyle {A ^ {2}} _ {3} = {R ^ {2}} _ {3} + {S ^ {2}} _ {3 } = (C) - (E) - (F) - (G) - (H)}$ jest dodawane do pojemnika $najkrótsza$ potencjalna k - ścieżka.

${\ displaystyle A ^ {2}}$ trzech ścieżek w kontenerze B, wybrano, aby stać się $ponieważ$ najniższy koszt 7. Proces ten jest kontynuowany do trzeciej k - najkrótszej ścieżki. Należy jednak zauważyć, że w ramach tej trzeciej iteracji niektóre ścieżki ostrogi nie istnieją. A ścieżka, która została wybrana, $się$ to ${\ Displaystyle (C) - (D) - (F) - (H)}$ .

Cechy

Złożoność przestrzeni

Aby zapisać krawędzie wykresu, najkrótsza lista $potencjalnie$${\ Displaystyle N ^ {2} + KN$ najkrótsza lista ścieżek , adresy pamięci $K.$ są wymagane. W gorszym $przypadku$ każdy węzeł na wykresie ma krawędź do każdego innego węzła na wykresie, dlatego są adresy Tylko $adresy$ są potrzebne dla obu list. $displaystyle A}$ i $ponieważ$$ścieżki ,$ najwyżej będą przechowywane tylko $przy czym każda$ może mieć węzły

Złożoność czasowa

Złożoność czasowa algorytmu Yena zależy od algorytmu najkrótszej ścieżki używanego do obliczania ścieżek bocznych, więc przyjmuje się algorytm Dijkstry. Algorytm Dijkstry ma gorszą złożoność czasową przypadku $O$ przy użyciu sterty Fibonacciego staje się $Displaystyle O$$.$ , gdzie jest liczbą krawędzi na wykresie Ponieważ algorytm Yen sprawia, że ${\ displaystyle Kl}$ wzywa Dijkstrę do obliczania bocznych ścieżek, gdzie $jest$ bocznych ścieżek. $N$ skondensowanym wykresie oczekiwana wartość to $N$$)} , podczas$ najgorszym przypadkiem jest . , złożoność czasowa staje się ${\ Displaystyle O (KN (M + N \ log N))}$ .

Ulepszenia

Algorytm jena można ulepszyć, używając sterty do przechowywania $potencjalnych$ k - najkrótszych ścieżek. Użycie sterty zamiast listy poprawi wydajność algorytmu, ale nie złożoność. Jedną z metod na nieznaczne zmniejszenie złożoności jest pominięcie węzłów, w których nie istnieją ścieżki ostrogi. Ten przypadek jest tworzony, gdy wszystkie ścieżki ostrogi z węzła ostrogi zostały użyte w poprzednim ${\ displaystyle A ^ {k}}$ . Ponadto, $ma$ K $Kk$$}$ ścieżki o minimalnej długości, w odniesieniu do tych w kontenerze można je wyodrębnić i wstawić do kontenera $ponieważ$ nie zostaną znalezione krótsze ścieżki.

modyfikacja Lawlera

Eugene Lawler zaproponował modyfikację algorytmu Yena, w której ścieżki duplikatów nie są obliczane, w przeciwieństwie do oryginalnego algorytmu, w którym są one obliczane, a następnie odrzucane, gdy okażą się duplikatami. Te zduplikowane ścieżki wynikają z obliczenia bocznych ścieżek węzłów w korzeniu ${\ displaystyle A ^ {k}}$ . Na przykład, $Displaystyle (i)}$ węźle $}$ odbiega od ${\ Displaystyle A ^ {k-1}$ . Każda ścieżka ostrogi, która jest obliczona, będzie duplikatem, ponieważ ${\ Displaystyle {S ^ {k}} _ {j}}$ gdzie ${\ Displaystyle j = 0, \ ldots, i}$ zostały już obliczone podczas iteracji. ${\ displaystyle k-1}$ . Dlatego należy obliczyć tylko ścieżki ostrogi dla $ścieżce$ ostrogi, ${\ Displaystyle {S ^ {k}} _ {h}}$ gdzie ${\ Displaystyle h}$ waha się od ${\ Displaystyle (i + 1) ^ {k-1}}$ do ${\ Displaystyle (Q_ {k}) ^ {k-1}}$ . Aby wykonać $ZA$ operację dla , potrzebny jest rekord identyfikujący węzeł, z którego rozgałęził się $Displaystyle A ^ {k-1}}$${\ Displaystyle A ^ {k-2}}$ .

Zobacz też

• Poprawa jena do algorytmu Bellmana-Forda

Linki zewnętrzne

• Implementacja Open Source C++
• Implementacja Open Source C++ przy użyciu biblioteki Boost Graph