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$

algorithms graphs

— gprime
źródło

Czego spróbowałeś do tej pory? Jeśli całkowicie utkniesz, zacznij od małej: jak naprawdę wyglądają wykresy unipatyczne? Na przykład narysuj każdy wykres unipatyczny jednym wierzchołkiem, dwoma wierzchołkami, trzema wierzchołkami i tak dalej. Możesz zauważyć pomocny wzór. Ponadto wspominasz, że nie ma ujemnych cykli masy - czy mogą być nawet cykle (o dowolnej masie)?

— Juho,

@mrm Jaki wzór masz na myśli? Wykresy unipatyczne mogą mieć cykle, w ograniczony sposób, którego nie mogę znaleźć łatwego sposobu wyrażenia.

— Gilles „SO- przestań być zły”

@ mrm Nie. Krawędź może należeć maksymalnie do jednego cyklu. Węzeł może należeć do dowolnej liczby cykli: wykres w kształcie gwiazdy -point jest unipatyczny (i możesz uzyskać jeszcze wyższy stosunek cykli elementarnych na węzeł).

n

$n$

E = ⋃_{i \leq n} {(a, b_{i}), (b_{i}, a)}

$E=\bigcup_{i\le n} \{(a,b_i),(b_i,a)\}$

— Gilles „SO- przestań być zły”

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$ $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 . $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 . $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. $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 ). $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$

— Gilles „SO- przestań być zły”
źródło