Negative Gewichte unter Verwendung des Dijkstra-Algorithmus

113

Ich versuche zu verstehen, warum der Dijkstra-Algorithmus nicht mit negativen Gewichten funktioniert. Wenn ich ein Beispiel für kürzeste Wege lese , versuche ich, das folgende Szenario herauszufinden:

    2
A-------B
 \     /
3 \   / -2
   \ /
    C

Von der Website:

Angenommen, die Kanten sind alle von links nach rechts gerichtet. Wenn wir mit A beginnen, wählt der Dijkstra-Algorithmus die Kante (A, x), die d (A, A) + Länge (Kante) minimiert, nämlich (A, B). Es setzt dann d (A, B) = 2 und wählt eine andere Kante (y, C), die d (A, y) + d (y, C) minimiert; Die einzige Wahl ist (A, C) und es wird d (A, C) = 3 gesetzt. Es findet jedoch nie den kürzesten Weg von A nach B über C mit der Gesamtlänge 1.

Ich kann nicht verstehen, warum bei Verwendung der folgenden Implementierung von Dijkstra d [B] nicht aktualisiert wird auf 1(Wenn der Algorithmus den Scheitelpunkt C erreicht, wird eine Relaxation für B ausgeführt, um sicherzustellen, dass d [B] gleich 2ist und daher aktualisiert wird seinen Wert zu 1).

Dijkstra(G, w, s)  {
   Initialize-Single-Source(G, s)
   S ← Ø
   Q ← V[G]//priority queue by d[v]
   while Q ≠ Ø do
      u ← Extract-Min(Q)
      S ← S U {u}
      for each vertex v in Adj[u] do
         Relax(u, v)
}

Initialize-Single-Source(G, s) {
   for each vertex v  V(G)
      d[v] ← ∞
      π[v] ← NIL
   d[s] ← 0
}

Relax(u, v) {
   //update only if we found a strictly shortest path
   if d[v] > d[u] + w(u,v) 
      d[v] ← d[u] + w(u,v)
      π[v] ← u
      Update(Q, v)
}

Vielen Dank,

Meir

Meir
quelle
Das Finden von Pfaden im Allgemeinen mit negativen Kantengewichten ist äußerst schwierig. Egal welche Route Sie finden, es besteht immer die Möglichkeit einer beliebig langen Route mit einem beliebig großen negativen Kantengewicht irgendwo entlang. Ich wäre nicht überrascht, wenn NP vollständig wäre.
Nick Johnson
4
Für alle anderen, die diesen Zweifel haben, finden Sie den kürzesten Weg in einem Diagramm, das GEGEBEN ist, dass es keine negativen Gewichtszyklen gibt. Der obige Algorithmus würde funktionieren, wenn die Relax-Funktion einen "wahren" Wert zurückgeben würde, wenn Relax tatsächlich erfolgreich war. In diesem Fall würde der benachbarte Scheitelpunkt "v" in die Prioritätswarteschlange eingereiht, wenn er nicht vorhanden ist, oder aktualisiert, wenn er bereits vorhanden ist. Dies bedeutet, dass besuchte Knoten erneut zur Prioritätswarteschlange hinzugefügt werden können, da sie immer entspannter werden.
Goelakash

Antworten:

202

Der von Ihnen vorgeschlagene Algorithmus findet zwar den kürzesten Pfad in diesem Diagramm, jedoch nicht alle Diagramme im Allgemeinen. Betrachten Sie zum Beispiel dieses Diagramm:

Abbildung des Diagramms

Angenommen, die Kanten sind wie in Ihrem Beispiel von links nach rechts gerichtet.

Ihr Algorithmus funktioniert wie folgt:

  1. Zuerst legen Sie d(A)auf zeround die anderen Distanzen infinity.
  2. Anschließend erweitern Sie den Knoten Aund setzen d(B)auf 1, d(C)auf zeround d(D)auf 99.
  3. Als nächstes erweitern Sie Cohne Nettoänderungen.
  4. Sie erweitern dann B, was keine Auswirkung hat.
  5. Schließlich erweitern Sie D, welche Änderungen d(B)zu -201.

Beachten Sie jedoch, dass dies am Ende d(C)immer noch der Fall ist 0, obwohl der kürzeste Weg CLänge hat -200. Ihr Algorithmus kann daher in einigen Fällen Entfernungen nicht genau berechnen. Selbst wenn Sie Rückzeiger speichern würden, die angeben, wie Sie von jedem Knoten zum Startknoten gelangen A, würden Sie am Ende den falschen Pfad von Cnach zurück nehmen A.

templatetypedef
quelle
35
Um Ihre ausgezeichnete Antwort zu ergänzen: Dijkstra als gieriger Algorithmus ist der Grund für seine kurzsichtige Wahl.
Blubb
4
Ich möchte darauf hinweisen, dass technisch gesehen alle Pfade in diesem Diagramm dank des negativen Zyklus A, D, B, A negative Unendlichkeitskosten verursachen.
Nate
2
@ Nate- Zur Verdeutlichung sind alle Kanten im Diagramm von links nach rechts gerichtet. Es war ziemlich schwierig, Pfeile in meiner hochwertigen ASCII-Grafik zu rendern. :-)
Templatetypedef
2
Für diejenigen, die noch keine Diagramme mit negativen Kanten gesehen haben, finde ich eine nützliche Interpretation dieses Diagramms als ein Netz mautpflichtiger Straßen, bei dem die Kantengewichte die von Ihnen gezahlte Maut angeben. Die Straße -300 ist eine verrückte mautpflichtige Straße, auf der Sie stattdessen 300 US-Dollar erhalten.
D Coetzee
3
@ SchwitJanwityanujit- So funktioniert der Algorithmus von Dijkstra. Der Algorithmus untersucht keine Pfade , sondern verarbeitet Knoten . Jeder Knoten wird genau einmal verarbeitet. Sobald wir den B-Knoten verarbeiten und feststellen, dass seine Entfernung 1 beträgt, werden wir den Knoten B niemals erneut besuchen oder versuchen, seine Entfernung zu aktualisieren.
Templatetypedef
25

Beachten Sie, dass Dijkstra auch für negative Gewichte funktioniert, wenn der Graph keine negativen Zyklen aufweist, dh Zyklen, deren summiertes Gewicht kleiner als Null ist.

Natürlich könnte man sich fragen, warum in dem Beispiel von templatetypedef Dijkstra versagt, obwohl es keine negativen Zyklen gibt, tatsächlich nicht einmal Zyklen. Dies liegt daran, dass er ein anderes Stoppkriterium verwendet, das den Algorithmus enthält, sobald der Zielknoten erreicht ist (oder alle Knoten einmal abgerechnet wurden, er hat dies nicht genau angegeben). In einem Diagramm ohne negative Gewichte funktioniert dies einwandfrei.

Wenn man das alternative Stoppkriterium verwendet, das den Algorithmus stoppt, wenn die Prioritätswarteschlange (Heap) leer ist (dieses Stoppkriterium wurde auch in der Frage verwendet), findet dijkstra den richtigen Abstand auch für Diagramme mit negativen Gewichten, jedoch ohne negative Zyklen.

In diesem Fall geht jedoch die asymptotische Zeitgrenze von dijkstra für Graphen ohne negative Zyklen verloren. Dies liegt daran, dass ein zuvor festgelegter Knoten wieder in den Heap eingefügt werden kann, wenn aufgrund negativer Gewichte ein besserer Abstand gefunden wird. Diese Eigenschaft wird als Etikettenkorrektur bezeichnet.

infty10000101
quelle
2. Es ist nicht klar, warum Sie denken, die Zeit würde mich "eher wie Bellman-Ford" und nicht exponentiell (was schlimmer ist als Bellman-Ford). Haben Sie einen konkreten Algorithmus und einen Beweis im Sinn?
Gassa
3
Zu 1.: Da Sie mit dem genannten Stoppkriterium genau die gleiche Implementierung von dijkstra verwenden können, die stoppt, wenn die Warteschlange leer ist (siehe Pseudocode in der ursprünglichen Frage), handelt es sich immer noch um den dijkstras-Algorithmus für kürzeste Pfade, obwohl er sich anders verhält Knoten mehrmals setzen (Etikettenkorrektur).
Infty10000101
1
Zu 2.: Das war nur eine Vermutung, also werde ich das löschen. Ich denke, Sie haben Recht mit der exponentiellen Zeit, da es exponentiell viele Wege gibt, die erkundet werden müssen.
Infty10000101
11

Sie haben S nirgendwo in Ihrem Algorithmus verwendet (außer es zu modifizieren). Die Idee von dijkstra ist, sobald ein Scheitelpunkt auf S liegt, wird er nie wieder geändert. In diesem Fall erreichen Sie B nicht mehr über C, sobald es sich in S befindet.

Diese Tatsache stellt die Komplexität von O (E + VlogV) sicher [andernfalls wiederholen Sie Kanten mehr als einmal und Scheitelpunkte mehr als einmal]

Mit anderen Worten, der von Ihnen veröffentlichte Algorithmus befindet sich möglicherweise nicht in O (E + VlogV), wie vom dijkstra-Algorithmus versprochen.

amit
quelle
Es ist auch nicht erforderlich, den Scheitelpunkt ohne Kanten mit negativem Gewicht zu ändern, was die Annahme, dass die Pfadkosten nur mit wiederholten Kanten
steigen
Diese Annahme ermöglicht es uns genau, S zu verwenden, und wenn ein Scheitelpunkt in S ist, wird er nie wieder geändert.
Amit
Ihre letzte Aussage ist falsch. Der veröffentlichte Algorithmus hat die Zeitkomplexität O (E + VlogV), wenn er an Graphen ohne negative Flanken arbeitet. Es ist nicht erforderlich zu überprüfen, ob wir einen Knoten bereits besucht haben, da die Tatsache, dass er besucht wurde, garantiert, dass das Entspannungsverfahren ihn nicht noch einmal in die Warteschlange einfügt.
Pixar
7

Da es sich bei Dijkstra um einen gierigen Ansatz handelt, wird ein Scheitelpunkt, der für diese Schleife als besucht markiert wurde, nie wieder neu bewertet, selbst wenn es einen anderen Pfad mit geringeren Kosten gibt, um ihn später zu erreichen. Ein solches Problem kann nur auftreten, wenn im Diagramm negative Flanken vorhanden sind.


Ein gieriger Algorithmus trifft , wie der Name schon sagt, immer die Wahl, die in diesem Moment die beste zu sein scheint. Angenommen, Sie haben eine Zielfunktion, die an einem bestimmten Punkt optimiert (entweder maximiert oder minimiert) werden muss. Ein Greedy-Algorithmus trifft bei jedem Schritt gierige Entscheidungen, um sicherzustellen, dass die Zielfunktion optimiert wird. Der Greedy-Algorithmus hat nur einen Schuss, um die optimale Lösung zu berechnen, sodass er niemals zurückgeht und die Entscheidung umkehrt.

Punchoyeah
quelle
4

TL; DR: Die Antwort hängt von Ihrer Implementierung ab. Für den von Ihnen geposteten Pseudocode funktioniert dies mit negativen Gewichten.


Varianten des Dijkstra-Algorithmus

Der Schlüssel ist, dass es drei Arten der Implementierung des Dijkstra-Algorithmus gibt , aber alle Antworten unter dieser Frage ignorieren die Unterschiede zwischen diesen Varianten.

  1. Verwenden eines verschachteltenfor Schleife zum Entspannen von Scheitelpunkten. Dies ist der einfachste Weg, um den Dijkstra-Algorithmus zu implementieren. Die zeitliche Komplexität ist O (V ^ 2).
  2. Priority-Queue / Heap-basierte Implementierung + KEIN Wiedereintritt erlaubt, wo Wiedereintritt bedeutet, dass ein entspannter Scheitelpunkt wieder in die Priority-Queue geschoben werden kann, um später wieder gelockert zu werden .
  3. Priority-Queue / Heap-basierte Implementierung + Wiedereintritt erlaubt.

Version 1 und 2 schlagen in Diagrammen mit negativen Gewichten fehl (wenn Sie in solchen Fällen die richtige Antwort erhalten, ist dies nur ein Zufall), aber Version 3 funktioniert weiterhin .

Der unter dem ursprünglichen Problem veröffentlichte Pseudocode ist die obige Version 3, daher funktioniert er mit negativen Gewichten.

Hier ist eine gute Referenz aus Algorithmus (4. Ausgabe) , die besagt (und die oben erwähnte Java-Implementierung von Version 2 und 3 enthält):

F. Funktioniert der Dijkstra-Algorithmus mit negativen Gewichten?

A. Ja und nein. Es gibt zwei Algorithmen mit kürzesten Pfaden, die als Dijkstra-Algorithmus bekannt sind, je nachdem, ob ein Scheitelpunkt mehr als einmal in die Prioritätswarteschlange eingereiht werden kann. Wenn die Gewichte nicht negativ sind, stimmen die beiden Versionen überein (da kein Scheitelpunkt mehr als einmal in die Warteschlange gestellt wird). Die in DijkstraSP.java implementierte Version (mit der ein Scheitelpunkt mehr als einmal in die Warteschlange gestellt werden kann) ist bei negativen Kantengewichten (aber keinen negativen Zyklen) korrekt, aber seine Laufzeit ist im schlimmsten Fall exponentiell. (Wir stellen fest, dass DijkstraSP.java eine Ausnahme auslöst, wenn der kantengewichtete Digraph eine Kante mit einem negativen Gewicht hat, sodass ein Programmierer von diesem exponentiellen Verhalten nicht überrascht ist.) Wenn wir DijkstraSP.java so ändern, dass ein Scheitelpunkt nicht in die Warteschlange gestellt werden kann mehr als einmal (z. B. mit einem markierten [] Array, um die entspannten Scheitelpunkte zu markieren),


Weitere Implementierungsdetails und die Verbindung von Version 3 mit dem Bellman-Ford-Algorithmus finden Sie in dieser Antwort von zhihu . Es ist auch meine Antwort (aber auf Chinesisch). Derzeit habe ich keine Zeit, es ins Englische zu übersetzen. Ich weiß es wirklich zu schätzen, wenn jemand dies tun und diese Antwort im Stackoverflow bearbeiten könnte.

Soloice
quelle
1

Überlegen Sie, was passiert, wenn Sie zwischen B und C hin und her gehen ... voila

(nur relevant, wenn der Graph nicht gerichtet ist)

Bearbeitet: Ich glaube, das Problem hat damit zu tun, dass der Pfad mit AC * nur dann besser sein kann als AB, wenn negative Gewichtskanten vorhanden sind. Es spielt also keine Rolle, wohin Sie nach AC gehen, unter der Annahme, dass dies nicht der Fall ist. negative Gewichtskanten Es ist unmöglich, einen Pfad zu finden, der besser als AB ist, wenn Sie B nach dem Wechselstrom erreicht haben.

prusswan
quelle
Dies ist nicht möglich, der Graph ist gerichtet.
Amit
@amit: guter Punkt, das habe ich verpasst. Zeit, das Problem zu überdenken
prusswan
1

"2) Können wir den Dijksra-Algorithmus für kürzeste Wege für Diagramme mit negativen Gewichten verwenden? Eine Idee kann sein, den Mindestgewichtswert zu berechnen, allen Gewichten einen positiven Wert (gleich dem absoluten Wert des Mindestgewichtswerts) hinzuzufügen und den Dijksra-Algorithmus auszuführen für den modifizierten Graphen. Funktioniert dieser Algorithmus? "

Dies funktioniert absolut nur, wenn alle kürzesten Pfade dieselbe Länge haben. Wenn beispielsweise bei einem kürzesten Pfad mit einer Länge von zwei Kanten und nach dem Hinzufügen eines Absolutwerts zu jeder Kante die Gesamtpfadkosten um 2 * | maximales negatives Gewicht | erhöht werden. Auf der anderen Seite ein anderer Pfad mit einer Länge von drei Kanten, so dass die Pfadkosten um 3 * | maximales negatives Gewicht | erhöht werden. Daher werden alle unterschiedlichen Pfade um unterschiedliche Beträge erhöht.

Verrückter Narr
quelle
0

Sie können den Algorithmus von dijkstra mit negativen Flanken ohne negativen Zyklus verwenden, aber Sie müssen zulassen, dass ein Scheitelpunkt mehrmals besucht werden kann und diese Version ihre schnelle Zeitkomplexität verliert.

In diesem Fall habe ich praktisch gesehen, dass es besser ist, einen SPFA-Algorithmus zu verwenden, der eine normale Warteschlange hat und negative Flanken verarbeiten kann.

CodingLab
quelle