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

14

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 tD=(V,A)stst

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 .

robowolverine
źródło

Odpowiedzi:

10

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.

jmite
źródło
2
Bellman-Ford to dynamiczny algorytm programowania.
Raphael
1
@Raphael tak, ale myślę, że istnieje bezpośredni algorytm DP, aby znaleźć maksymalną ścieżkę, zamiast negować wszystkie wagi krawędzi.
jmite
1
@jmite: Oczywiście: po prostu zmień Bellmana-Forda, aby dokonać konwersji online lub zmaksymalizować, albo ...
Raphael
1
Nawiasem mówiąc, nie jestem intuicyjnie przekonany, że najdłuższa ścieżka NP-zupełna jest zatem łatwo dostępna w P na DAG. Byłbym wdzięczny za dowód / referencję / wyjaśnienie.
Raphael
2
Istnieje również prostszy i wydajny algorytm DP dla DAG
8

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 tn=|V(G)|m=|E(G)|w(ab)(ab)st

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.bmin(b)max(b)b

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

    • Jeśli , zapisz .b=smin(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 .
      min(b):=minab[w(ab)+min(a)]max(b):=maxab[w(ab)+max(a)]
      b min ( b ) : = max ( b ) : = i n a c c e s s i b l emin(a)=max(a)=inaccessiblebmin(b):=max(b):=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)

Niel de Beaudrap
źródło
To rekurencyjne podejście „pull” może być faktycznie wolniejsze niż zwykłe dynamiczne podejście „push” i wymaga stosu wielkości liniowej do obsługi rekurencji. Zwykle podejście polega na ułożeniu wierzchołków w kolejności topologicznej i poprawie tymczasowego minimum i maksimum dla każdego sąsiada bieżącego węzła. Bieżący węzeł ma zawsze końcową wartość minimalną i maksymalną, ponieważ wszystkie krawędzie wejściowe muszą być już użyte do ich ulepszenia.
Palec