Jaki jest najszybszy algorytm znajdowania wszystkich najkrótszych ścieżek na rzadkim wykresie?

24

Na nieważonym wykresie bezkierunkowym z wierzchołkami i krawędziami takimi jak , jaki jest najszybszy sposób znalezienia wszystkich najkrótszych ścieżek na wykresie? Czy można to zrobić szybciej niż Floyd-Warshall, który jest ale bardzo szybki na iterację? $V$ $E$ $2V \gt E$ $O(V^3)$

Co powiesz na ważenie wykresu?

algorithms graphs shortest-path

— Jakob Weisblat
źródło

32

Ponieważ jest to wykres nieważony, można uruchomić pierwsze wyszukiwanie szerokości (BFS) z każdego wierzchołka na wykresie. Każde uruchomienie BFS daje najkrótsze odległości (i ścieżki) od wierzchołka początkowego do każdego innego wierzchołka. Złożoność czasowa dla jednego BFS wynosi ponieważ na twoim rzadkim wykresie. Uruchamianie go razy daje złożoność czasową . $v$ $O(V + E) = O(V)$ $E = O(V)$ $V$ $O(V^2)$

W przypadku ważonego grafu kierunkowego algorytm Johnsona, sugerowany przez Yuvala, jest najszybszy dla grafów rzadkich. Wymaga które w twoim przypadku okazuje się być . W przypadku ważonego niekierowanego wykresu można uruchomić algorytm Dijkstry $O(V^2\log V + VE)$ $O(V^2\log V)$ z każdego węzła lub zamień każdą nieukierowaną krawędź na dwie przeciwnie skierowane krawędzie i uruchom algorytm Johnsona. Oba będą dawały takie same czasy aysmptotyczne jak powyższy algorytm Johnsona dla twojego rzadkiego przypadku. Zauważ też, że wspomniane powyżej podejście BFS działa zarówno dla grafów skierowanych, jak i niekierowanych.

— Paresh
źródło

7

Istnieje algorytm Johnsona , którego czas działania wynosi . $O(V^2\log V + VE)$

— Yuval Filmus
źródło

7

Możesz spróbować stworzyć wersję Floyd-Warshall, która będzie szybsza na rzadkich matrycach.

Najpierw przypomnijmy sobie, co robi ten algorytm:

Niech będzie macierzą odległości. Na początku algorytmu jest waga krawędzi . Jeśli to krawędź nie istnieje wówczas . $M$ $M_{i,j}$ $i \rightarrow j$ $M_{i,j}=\infty$

Algorytm ma kroków. W kroku algorytmu dla każdej pary węzłów ustawiamy $V$ $k$ $i,j$

{M.}_{ja, jot} \leftarrow min {{M.}_{ja, jot}, {M.}_{ja, k} + {M.}_{k, jot}} .

$M_{i,j} \leftarrow \min\{M_{i,j}, M_{i,k}+M_{k,j}\}.$

$M_{i,k}=\infty$ $M_{k,j}=\infty$ $deg_{in}(k) \cdot deg_{out}(k)$ $deg_{in}(k)$ $deg_{out}(k)$ $k$ $M$

$k$

$E=O(V)$ $k=0$ $O(1)$ $M$ $O(V)$ $k=|V|$ $O(V^2)$ $O(V^3)$

— Amit Moscovich
źródło