Znajdowanie wszystkich najkrótszych ścieżek od źródła do wszystkich wierzchołków w dwuwymiarowym algorytmie, algorytmie wykresu, najkrótszej ścieżce, ukierunkowanym wykresie

Otrzymujemy ukierunkowany wykres G (prawdopodobnie z cyklami) z dodatnimi masami krawędzi i minimalną odległością D[v] do każdego wierzchołka v ze źródła podano również s (D jest tablicą w ten sposób). Problem polega na znalezieniu tablicy N[v] = number ścieżek długości D[v] od s do v, w czasie liniowym.

Teraz jest to problem z pracą domową, w którym byłemzmagam się z tym dość długo. Pracowałem nad następującą myślą: „Próbuję usunąć cykle, odpowiednio wybierając acykliczny podgraf G, a następnie spróbuję znaleźć najkrótsze ścieżki od s do v w podgrafie.

Ale nie potrafię jednoznacznie ustalić, co robić, więc doceniam każdą pomoc, jak w jakościowym pomyśle, co robić.

Odpowiedzi:

Możesz użyć Programowanie dynamiczne podejdź tutaj i uzupełnij liczbę ścieżek, gdy jedziesz, jeśli D[u] + w(u,v) = D[v], coś jak:

N = [0,...,0]
N[s] = 1 //empty path
For each vertex v, in *ascending* order of `D[v]`:
for each edge (u,v) such that D[u] < D[v]:
if D[u] + w(u,v) = D[v]: //just found new shortest paths, using (u,v)!
N[v] += N[u]

Złożoność jest O(VlogV + E), zakładając, że wykres nie jest rozproszony, O(E) dominuje.

Wyjaśnienie:

Jeśli jest najkrótsza ścieżka v0->v1->...->v_(k-1)->v_k od v0 do v_k, następnie v0->...->v_(k-1) jest najkrótsza ścieżka od v0 do v_k-1, a więc - podczas iteracji v_k - N[v_(k-1)] był już w pełni obliczony (pamiętaj, wszystkie krawędzie mają dodatnie wagi i D[V_k-1] < D[v_k]i powtarzamy, zwiększając wartość D[v]).
Dlatego ścieżka v0->...->v_(k-1) jest liczony w liczbie N[V_(k-1)] w tym momencie.
Od v0->...->v_(k-1)-v_k jest najkrótszą ścieżką - to znaczy D[v_(k-1)] + w(v_k-1,v_k) = D[v_k] - więc warunek zostanie zachowany, a my dodamy liczbę tej ścieżki do N[v_k].

Zauważ, że dowód dla tego algorytmu będzie zasadniczo indukcją, która będzie bardziej formalnie zgodna z wytycznymi tego wyjaśnienia.