Znajdź najkrótsze ścieżki na zważonym wykresie unipatycznym

Mówi się, że ukierunkowany wykres jest unipatyczny, jeśli dla dowolnych dwóch wierzchołków i na wykresie istnieje co najwyżej jedna prosta ścieżka od do .$u$$v$$G=(V,E)$$u$$v$

Załóżmy, że otrzymałem wykres jednoczynnościowy taki, że każda krawędź ma dodatnią lub ujemną wagę, ale nie zawiera żadnych ujemnych cykli masy.$G$

Z tego chcę znaleźć algorytm, który wyszukuje wszystkie najkrótszej ścieżki do wszystkich węzłów od węzła źródłowego .$O(|V|)$$s$

Nie jestem pewien, jak bym podszedł do tego problemu. Próbuję zobaczyć, jak mógłbym wykorzystać fakt, że nie zawiera on żadnych ujemnych cykli wagi i oczywiście co najwyżej jedną prostą ścieżkę między dowolnym węzłem do .$u$$v$

Wybierz reprezentację danych

Najpierw spójrz na rozmiar wyniku. Chcesz kolekcji najkrótszych ścieżek od do każdego innego węzła. O ile średnia długość ścieżki nie jest ograniczona stałą (co nie jest: żadna lista jest ścieżką unipath, a jeśli weźmiesz root jako całkowita długość ścieżek wynosi gdzie jest długość listy), musisz zachować ostrożność w reprezentacji danych: struktura zawierająca ścieżki będzie musiała korzystać z udostępniania między ścieżkami.s n ( n - 1 ) / 2 $s$$s$$n(n-1)/2$$n$

Z wyłączeniem cykli, istnieje jedna ścieżka od do dowolnego innego węzła . Jeśli ścieżka ta przechodzi przez węzeł pośredni , wówczas pierwszym segmentem ścieżki jest żądana ścieżka od do . u t s $s$$u$$t$$s$$t$

Proponuję zapisać wynik w tablicy indeksowanej według węzłów o numerach od do , przy czym . Każdy element w tablicy przechowuje indeks poprzedniego węzła na ścieżce do tego węzła (użyj np. jako specjalnego znacznika dla węzłów, które są nieosiągalne od ). Ścieżka od do będzie .| E | - 1 s = 0 - 1 s s t ( s = R [ … R [ t ] … ] , … , R [ R [ t ] ] , R [ t ] , t $0$$|E|-1$$s=0$$-1$$s$$s$$t$$(s=R[\ldots R[t]\ldots],\ldots,R[R[t]],R[t],t)$

Przejdź przez wykres

Zainicjuj dla wszystkich .- $R$$-1$

Wykonaj przemierzanie wykresu w pierwszej kolejności lub w pierwszej szerokości, zaczynając od . Za każdym razem, gdy osiągany jest węzeł , ustaw na jego poprzednika.u R [ u $s$$u$$R[u]$

Ponieważ istnieją cykle, węzeł może zostać osiągnięty więcej niż jeden raz. Mając wskazuje, że już zostały otwarte.$R[u] \ne -1$$u$

Udowodnij poprawność

Ze względu na właściwość unipatyczną nie ma znaczenia, w jaki sposób docieramy do każdego węzła, o ile nie ukończyliśmy cyklu. Jest tylko jedna prosta ścieżka.

Udowodnij złożoność

Algorytm może dotrzeć do każdego węzła więcej niż raz, więc nie jest jasne, czy jego złożoność wynosi . praca to w rzeczywistości gdzie to krawędzie, które są dostępne ze źródła. Dokładniej, do węzła dochodzimy więcej niż raz tylko w jednej sytuacji: jeśli węzeł jest pierwszym, który osiągamy w danym cyklu, iw tym przypadku osiągamy go dwukrotnie (raz z prostej ścieżki i raz po ukończeniu cyklu ).Θ ( | E 0 | ) V $O(|V|)$$\Theta(|E_0|)$$V_0$

No więc. Udowodnijmy, że na grafie unipatycznym liczba cykli elementarnych rośnie co najwyżej liniowo wraz z liczbą węzłów. (Cykl elementarny to taki, który nie zawiera krótszego cyklu.) W poniższej dyskusji założę, że wykres nie ma własnej krawędzi (żadnej krawędzi od węzła do siebie; takie krawędzie i tak nie mają znaczenia dla konstrukcji ścieżki ).

Wykresy unipatyczne mogą mieć cykle, ale w bardzo ograniczony sposób. Byłoby miło, gdybyśmy mogli jakoś powiązać każdy cykl z odrębnym węzłem (lub przynajmniej co najwyżej ograniczoną liczbą cykli na węzeł). Czy cykle mogą współdzielić węzeł? Niestety tak.

Możesz mieć cykli współużytkujących jeden węzeł i żadnych innych węzłów. Powstały wykres jest jednoznaczny. W przypadku cykli o długości 2 jest to wzór gwiazdy z centralnym węzłem i dowolną liczbą węzłów tak że .$m$$a$$a$$b_i$$\forall i, a \leftrightarrows b_i$

Więc będziemy musieli pracować ciężej. Spróbujmy to udowodnić indukcyjnie. Niech będzie liczbą węzłów na wykresie , liczbą krawędzi, a liczbą cykli elementarnych, które nie są krawędziami własnymi. Twierdzę, że jeśli jest jednoznaczny i nie jest pusty, to .$\#V(G)$$G$$\#E(G)$$\#C(G)$$G$$\#C(G) \le \#V(G)-1$

Jest to oczywiste w przypadku wykresu z jednym lub dwoma węzłami. Załóżmy, że twierdzenie to dotyczy wszystkich grafów, tak że i niech będzie grafem unipatycznym z węzłami. Jeśli nie ma cyklu, , obudowa zamknięta. W przeciwnym razie niech będzie cyklem elementarnym.$\#V(G) < n$$G$$n$$G$$0 = \#C(G) < \#V(G)$$(a_1,\ldots,a_m)$

Zwiń cykl: niech będzie wykresem, którego węzłami są minus plus węzeł a których krawędzie są wszystkimi krawędziami nie obejmującymi , plus ilekroć oraz ilekroć . Każda ścieżka w indukuje ścieżkę w (jeśli ścieżka obejmuje , to zastąp ją przez$G'$$G$$\{a_1,\ldots,a_m\}$$a$$G$$a_i$$a \rightarrow_{G'} b$$\exists i, a_i \rightarrow_G b$$b \rightarrow_{G'} a$$\exists i, b \rightarrow_G a_i$$G'$$G$$b \rightarrow a \rightarrow c$$b \rightarrow a_i \rightarrow a_{i+1} \rightarrow \ldots \rightarrow a_j \rightarrow c$ in ). Dlatego jest unipatyczne. Ponadto, ponieważ cykle w nie dzielą krawędzi, ma wszystkie cykle w oprócz tego, który wyeliminowaliśmy: . Poprzez indukcję . Ponieważ , mamy .$G$$G'$$G$$G'$$G$$\#C(G') = \#C(G)-1$$\#C(G') \le \#V(G')-1$$\#V(G') = \#V(G) - m + 1$$\#C(G) = \#C(G')+1 \le \#V(G) - m = n-m \le n-1$

To kończy dowód. Przejście następuje co najwyżej krawędzi.$2|V|-2$