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

Na nieważonym wykresie bezkierunkowym z wierzchołkami i krawędziami E, takimi jak 2 V > E , 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 O ( V 3 ), ale bardzo szybki na iterację?$V$$E$$2V \gt E$$O(V^3)$

Co powiesz na ważenie wykresu?

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 O ( V + E ) = O ( V ), ponieważ E = O ( V ) na twoim rzadkim wykresie. Uruchamianie go V razy daje złożoność czasową O ( V 2 ) .$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ć O ( V 2 log V ) . 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.

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

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 M í , j jest waga krawędzi i → j . Jeśli to krawędź nie istnieje wówczas M I , J = ∞ .$M$$M_{i,j}$$i \rightarrow j$$M_{i,j}=\infty$

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

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