Znajdowanie najkrótszych i najdłuższych ścieżek między dwoma wierzchołkami w DAG

Biorąc pod uwagę nieważony DAG (skierowane acykliczny wykres) oraz dwa wierzchołki i , jest możliwe znalezienie najkrótszej ścieżki, a najdłuższy z na w czasie wielomianowym? Długości ścieżek są mierzone liczbą krawędzi.s t s $D = (V,A)$$s$$t$$s$$t$

Interesuje mnie znalezienie zakresu możliwych długości ścieżek w czasie wielomianowym.

Ps., To pytanie jest duplikatem pytania StackOverflow Najdłuższa ścieżka w DAG .

W przypadku problemu z najkrótszą ścieżką, jeśli nie dbamy o wagi, pierwsze wyszukiwanie szerokości jest pewnym sposobem. W przeciwnym razie algorytm Dijkstry działa, o ile nie ma ujemnych krawędzi.

Aby uzyskać najdłuższą ścieżkę, zawsze możesz wykonać Bellmana-Forda na wykresie z zanegowanymi wszystkimi wagami krawędzi. Przypomnij sobie, że Bellman-Ford działa tak długo, jak długo nie ma ujemnych cykli masy, a zatem działa z dowolnymi obciążnikami na DAG.

Niechi. Niech oznacza ciężar krawędzi . Załóżmy, że chcesz znaleźć minimalny i maksymalny koszt ścieżki od do .m = | E ( G ) | w ( a → b ) ( a → b ) s $n = |V(G)|$$m = |E(G)|$$w(a \to b)$$(a \to b)$$s$$t$

Począwszy od , wykonaj następujące czynności:$b := t$

1. Jeśli zostało już odwiedzone, zwróć już obliczone i . W przeciwnym razie oznacz jako odwiedzone.$b$$\min(b)$$\max(b)$$b$

2. Określ i zapisz i w następujący sposób.$\min(b)$$\max(b)$

   • Jeśli , zapisz .$b = s$$\min(s) := \max(s) := 0$
   • W przeciwnym razie ustaw ignorując wierzchołki, dla których . Podczas obliczania minimum i maksimum dla pustego zestawu krawędzi (brak krawędzi przychodzących do lub wszystkie ignorowane), ustaw . $$\begin{align*}\min(b) &:= \min_{a \to b} \Bigl[ w(a \to b) + \min(a) \Bigr] \\ \max(b) &:= \max_{a \to b} \Bigl[ w(a \to b) + \max(a) \Bigr]\end{align*}$$ b min ( b ) : = max ( b ) : = i n a c c e s s i b l $\min(a) = \max(a) = \mathrm{inaccessible}$$b$$\min(b) := \max(b) := \mathrm{inaccessible}$

Powinieneś być w stanie udowodnić, że ten algorytm działa w czasie , pomijając czas wymagany do zainicjowania wszystkich zmiennych wierzchołków.$O(m)$