Oto ćwiczenie:

Niech v i będą dwoma wierzchołkami w grafie skierowanym G = (V, E). Zaprojektuj algorytm czasu liniowego, aby znaleźć liczbę różnych najkrótszych ścieżek (niekoniecznie rozłącznych wierzchołków) między v i w. Uwaga: krawędzie w G są nieważone

Dla tej akcyzy podsumowuję następująco:

Jest to ukierunkowany wykresProsi oliczba różnych najkrótszych ścieżek. Po pierwsze, ścieżki powinny być najkrótsze, wtedy może być więcej niż jedna taka najkrótsza ścieżka, której długość jest taka sama.między v i w, więc zarówno v do w i od w do v powinny być policzone.liniowy czas.Wykres nie jest ważony.

Z powyższych punktów mam następujące myśli:

Nie potrzebuję używaćAlgorytm Dijkstry ponieważ wykres nie jest ważony i próbujemy znaleźć wszystkie najkrótsze ścieżki, a nie tylko jedną.Utrzymujęcount dla liczby najkrótszych ścieżekChciałbym najpierw użyć BFS z v, a także zachowaćglobal level InformacjaZwiększamglobal level o jeden za każdym razem, gdy BFS osiągnie nowy poziomUtrzymuję takżeshortest level informacja o najkrótszej drodze do wPo raz pierwszy spotykam się w podróży, przypisujęglobal level doshortest level icount++;tak długo jakglobal level równa sięshortest level, Zwiększamcount za każdym razem spotykałem się ponownie.jeśliglobal level staje się większy niżshortest level, Kończę podróż, ponieważ szukam najkrótszej ścieżki, a nie ścieżki.Następnie ponownie wykonuję 2 - 8 dla w do v

Czy mój algorytm jest poprawny? Jeśli wykonam v do w, a następnie w do v, czy jest to nadal uważane za czas liniowy?