Algorytm znajdujący liczbę prostych ścieżek od do w

Ktoś może zaproponować mi liniowy algorytmu czasu, który wprowadzany jest skierowany acykliczny wykres a dwa wierzchołki i i powraca liczbę prostych odcinków z na w . Mam algorytm, w którym uruchomię DFS (Głębokie pierwsze wyszukiwanie), ale jeśli DFS znajdzie to nie zmieni koloru (z białego na szary) żadnego z węzłów, które znajdują się na ścieżce tak że jeśli jest to podścieżka jakiejkolwiek innej ścieżki, to również DFS ponownie przechodzi przez tę podścieżkę. Na przykład rozważ listę przyległości, w której musimy znaleźć liczbę ścieżek od do vs t s t G t s ⇝ t p $G=(V,E)$$s$$t$$s$$t$$G$
$t$$s \rightsquigarrow t$$p$$v$ .

$$\begin{array}{|c|c c c|} \hline p &o &s &z \\ \hline o &r &s &v\\ \hline s &r \\ \hline r &y \\ \hline y &v \\ \hline v &w \\ \hline z & \\ \hline w &z \\ \hline \end{array}$$ Tutaj DFS rozpocznie się od $p$ a następnie powiedzmy, że idzie do $p \rightsquigarrow z$ ponieważ nie napotyka $v$ DFS będzie działał normalnie. Teraz drugi ścieżka jest $psryv$ ponieważ napotyka $v$ , nie zmieniamy koloru wierzchołków $s,r,y,v$ na szary. Następnie ścieżka $pov$ ponieważ kolor $v$ jest nadal biały. Następnie ścieżka posryv,$posryv$ ponieważ kolor $s$ jest biały i podobnie ścieżka$poryv$.Utrzymywany jest również licznik, który zwiększa się, gdy napotka $v$ .

Czy mój algorytm jest poprawny? jeśli nie, jakie modyfikacje są potrzebne, aby było poprawne, lub wszelkie inne podejścia będą bardzo mile widziane.

Uwaga : Rozważyłem tutaj algorytm DFS podany w książce „Wprowadzenie do algorytmów przez Cormena”, w którym koloruje on węzły zgodnie z jego statusem, więc jeśli węzeł nie jest odwiedzany, niezbadany i badany, wówczas kolor będzie biały, odpowiednio szary i czarny. Wszystkie pozostałe elementy są standardowe.

Twoja obecna implementacja obliczy prawidłową liczbę ścieżek w DAG. Jednak nie oznaczanie ścieżek zajmie wykładniczy czas. Na przykład na poniższej ilustracji każdy etap DAG zwiększa całkowitą liczbę ścieżek o wielokrotność 3. Ten wykładniczy wzrost można rozwiązać za pomocą programowania dynamicznego.

Obliczenie liczby ścieżek - w DAG jest określone przez powtarzalność, $s$$t$

$$\text{Paths}(u) = \begin{cases} 1 & \text{if } u = t \\ \sum_{(u,v) \in E} \text{Paths}(v) & \text{otherwise.}\\ \end{cases}$$

Prosta modyfikacja DFS obliczy to jako

def dfs(u, t):
    if u == t:
        return 1
    else:
        if not u.npaths:
            # assume sum returns 0 if u has no children
            u.npaths = sum(dfs(c, t) for c in u.children)
        return u.npaths

Nietrudno zauważyć, że każda krawędź jest oglądana tylko raz, stąd środowisko uruchomieniowe .$O(V + E)$

Trzeba tylko zauważyć, że liczba ścieżek od jednego węzła do węzła docelowego jest sumą liczby ścieżek od jego potomków do celu. Wiesz, że ten algorytm zawsze się zatrzyma, ponieważ twój wykres nie ma żadnych cykli.

Teraz, jeśli zapiszesz liczbę ścieżek z jednego węzła do celu podczas odwiedzania węzłów, złożoność czasu stanie się liniowa w liczbie wierzchołków, a pamięć liniowa w liczbie węzłów.

Liczbę ścieżek między dowolnymi dwoma wierzchołkami w DAG można znaleźć za pomocą reprezentacji macierzy przyległości.

Załóżmy, że A jest macierzą przylegania G. Biorąc moc Kth z A po dodaniu do niej macierzy tożsamości, daje liczbę ścieżek o długości <= K.

Ponieważ maksymalna długość dowolnej prostej ścieżki w DAG wynosi | V | -1, obliczenie | V | -1 potęgi dałoby liczbę ścieżek między wszystkimi parami wierzchołków.

Obliczenia | V | -1 mocy można dokonać wykonując logarytmiczne (| V | -1) wielokrotności każdego z TC: | V | ^ 2.