Finden der kürzesten und längsten Pfade zwischen zwei Eckpunkten in einer DAG

14

Ist es bei einem ungewichteten DAG (gerichteter azyklischer Graph) D=(V,A) und zwei Eckpunkten und möglich, den kürzesten und längsten Weg von nach in der Polynomzeit zu finden? Pfadlängen werden durch die Anzahl der Kanten gemessen.stst

Ich bin daran interessiert, den Bereich der möglichen Pfadlängen in der Polynomzeit zu finden.

Ps., Diese Frage ist ein Duplikat der StackOverflow-Frage Längster Pfad in einer DAG .

Robowolverine
quelle

Antworten:

10

Für das Problem des kürzesten Pfades ist die Breitensuche ein todsicherer Weg , wenn wir uns nicht um Gewichte kümmern . Andernfalls arbeitet der Dijkstra-Algorithmus, solange keine negativen Flanken vorliegen.

Für den längsten Weg können Sie immer Bellman-Ford in der Grafik mit allen negierten Kantengewichten ausführen. Denken Sie daran, dass Bellman-Ford funktioniert, solange es keine negativen Gewichtszyklen gibt, und daher mit allen Gewichten an einer DAG arbeitet.

jmite
quelle
2
Bellman-Ford ist ein dynamischer Programmieralgorithmus.
Raphael
1
@Raphael ja, aber ich denke, es gibt einen direkten DP-Algorithmus, um den maximalen Pfad zu finden, anstatt alle Kantengewichte zu negieren.
Jmite
1
@jmite: Warum, natürlich: Ändern Sie einfach Bellman-Ford, um die Konvertierung online durchzuführen, oder maximieren Sie oder ...
Raphael
1
Übrigens bin ich nicht intuitiv davon überzeugt, dass das NP-vollständige Problem Longest Path auf DAGs daher leicht in P vorkommt. Ich würde mich über einen Beweis / Hinweis / eine Erklärung freuen.
Raphael
2
Es gibt auch einen einfacheren und effizienteren DP-Algorithmus für DAG
8

Sei und m = | E ( G ) | . Sei w ( a b ) das Gewicht der Kante ( a b ) . Angenommen, Sie möchten die minimalen und maximalen Pfadkosten von s bis t ermitteln .n=|V(G)|m=|E(G)|w(ab)(ab)st

Führen Sie ausgehend von Folgendes aus:b:=t

  1. Wenn bereits besucht wurde, geben Sie die bereits berechneten Werte für min ( b ) und max ( b ) zurück . Ansonsten markiere b als besucht.bmin(b)max(b)b

  2. Bestimmen und notieren Sie und max ( b ) wie folgt.min(b)max(b)

    • Wenn , speichere min ( s ) : = max ( s ) : = 0 .b=smin(s):=max(s):=0
    • Sonst setze Ignorieren von Eckpunkten, für diemin(a)=max(a)=inaccessible. Wenn Sie ein Minimum und ein Maximum für eine leere Gruppe von Kanten berechnen (keine eingehenden Kanten fürboder alle ignoriert), legen Siemin(b) fest:
      min(b):=minab[w(ab)+min(a)]max(b):=maxab[w(ab)+max(a)]
      min(a)=max(a)=inaccessibleb .min(b):=max(b):=inaccessible

Sie sollten in der Lage sein zu beweisen, dass dieser Algorithmus in der Zeit , wobei die Zeit vernachlässigt wird, die zum Initialisieren aller Scheitelpunktvariablen erforderlich ist.O(m)

Niel de Beaudrap
quelle
Dieser rekursive "Pull" -Ansatz ist möglicherweise langsamer als der übliche dynamische "Push" -Ansatz und benötigt einen Stapel linearer Größe, um die Rekursion zu verarbeiten. Der übliche Ansatz besteht darin, Eckpunkte in einer topologischen Reihenfolge zu nehmen und das Zwischenminimum und -maximum für jeden Nachbarn des aktuellen Knotens zu verbessern. Der aktuelle Knoten hat immer den Endwert Minimum und Maximum, da alle eingehenden Kanten bereits verwendet wurden, um sie zu verbessern.
Palec,