Warum funktioniert der Dijkstra-Algorithmus nicht für Kanten mit negativer Gewichtung?

121

Kann mir jemand sagen, warum der Dijkstra-Algorithmus für den kürzesten Pfad einer Quelle davon ausgeht, dass die Kanten nicht negativ sein dürfen.

Ich spreche nur von Kanten, nicht von negativen Gewichtszyklen.

Madu
quelle
3
Eine richtige Antwort mit einem guten Beispiel wäre: stackoverflow.com/questions/6799172/…
Amitk

Antworten:

175

Denken Sie daran, dass im Dijkstra-Algorithmus, sobald ein Scheitelpunkt als "geschlossen" (und außerhalb der offenen Menge) markiert ist - der Algorithmus hat den kürzesten Weg dorthin gefunden und muss diesen Knoten nie wieder entwickeln - er den dazu entwickelten Pfad annimmt Weg ist der kürzeste.

Aber mit negativen Gewichten - es könnte nicht wahr sein. Beispielsweise:

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

Dijkstra aus A wird zuerst C entwickeln und später nicht finden A->B->C


BEARBEITEN Sie eine etwas tiefere Erklärung:

Es ist zu beachten, dass dies wichtig ist, da der Algorithmus in jedem Relaxationsschritt davon ausgeht, dass die "Kosten" für die "geschlossenen" Knoten tatsächlich minimal sind und daher der Knoten, der als nächstes ausgewählt wird, ebenfalls minimal ist.

Die Idee dabei ist: Wenn wir einen Scheitelpunkt so offen haben, dass seine Kosten minimal sind - durch Hinzufügen einer positiven Zahl zu einem Scheitelpunkt - wird sich die Minimalität niemals ändern.
Ohne die Beschränkung auf positive Zahlen ist die obige Annahme nicht wahr.

Da wir "wissen", dass jeder Scheitelpunkt, der "geschlossen" wurde, minimal ist - wir können den Entspannungsschritt sicher ausführen - ohne "zurückzublicken". Wenn wir zurückblicken müssen, bietet Bellman-Ford eine rekursive (DP) Lösung dafür an.

amit
quelle
5
Entschuldigung, aber ich erhalte keine Fehlermeldung. Zuerst A->Bwird 5 und A->Cwird 2. Dann B->Cwird -5. Der Wert von Cwird also der -5gleiche sein wie bei bellman-ford. Wie gibt das nicht die richtige Antwort?
Anirban Nag 'tintinmj'
5
@tintinmj zuerst "schließt" Dijkstra den Knoten Amit dem Wert 0. Dann wird der Knoten mit dem minimalen Wert angezeigt, Bist 5 und Cist 2. Der minimale Wert ist C, also wird er Cmit dem Wert 2 geschlossen und wird niemals zurückblicken, wenn später Bgeschlossen wird, kann es den Wert von nicht ändern C, da es bereits "geschlossen" ist.
Am
4
@amit Wie findet der Dijkstra-Algorithmus den Pfad nicht A -> B -> C? Es wird zuerst Cdie Entfernung auf 2 und dann Bdie Entfernung auf 5 aktualisiert . Angenommen, in Ihrem Diagramm gibt es keine ausgehenden Kanten von C, dann tun wir beim Besuch nichts C(und die Entfernung beträgt immer noch 2). Dann besuchen wir die Dbenachbarten Knoten, und der einzige benachbarte Knoten ist C, dessen neue Entfernung -5 beträgt. Beachten Sie, dass in der Dijkstra - Algorithmus, halten wir auch den Überblick über die Eltern , von denen wir erreichen (und Aktualisierung) der Knoten, und tun es aus C, Sie werden die Eltern erhalten B, und dann A, was zu einem korrekten Ergebnis. Was vermisse ich?
nbro
12
@amit Das Problem mit Ihrer Argumentation (glaube ich) und ich habe andere Leute gesehen, die es (seltsamerweise) getan haben, ist, dass Sie denken, der Algorithmus wird Knoten, deren kürzeste Entfernung bereits bestimmt wurde (und mit denen wir fertig sind), nicht erneut prüfen. Dies ist jedoch nicht korrekt, und deshalb haben wir den Schritt "Entspannung" ... Wir durchlaufen alle Knoten des Graphen und durchlaufen für jeden von ihnen die benachbarten Knoten, selbst wenn einer der benachbarten Knoten dies könnte wurden beispielsweise bereits aus unserer Warteschlange mit Mindestpriorität entfernt.
nbro
10
@amit Überprüfen Sie diese Antwort auf eine ähnliche Frage, bei der das Beispiel tatsächlich Sinn macht: stackoverflow.com/a/6799344/3924118
nbro
37

Betrachten Sie das unten gezeigte Diagramm mit der Quelle als Vertex A. Versuchen Sie zunächst, den Dijkstra-Algorithmus selbst darauf auszuführen.

Geben Sie hier die Bildbeschreibung ein

Wenn ich mich in meiner Erklärung auf den Dijkstra-Algorithmus beziehe, werde ich über den Dijkstra-Algorithmus sprechen, wie er unten implementiert ist.

Dijkstra-Algorithmus

Beginnen Sie also mit den Werten ( dem Abstand von der Quelle zum Scheitelpunkt ), die ursprünglich jedem Scheitelpunkt zugewiesen wurden:

Initialisierung

Wir extrahieren zuerst den Scheitelpunkt in Q = [A, B, C], der den kleinsten Wert hat, dh A, wonach Q = [B, C] . Hinweis A hat eine gerichtete Kante zu B und C, beide sind auch in Q, daher aktualisieren wir beide Werte.

erste Iteration

Jetzt extrahieren wir C als (2 <5), jetzt Q = [B] . Beachten Sie, dass C mit nichts verbunden ist, sodass die line16Schleife nicht ausgeführt wird.

zweite Iteration

Schließlich extrahieren wir B, wonach Q ist Phi. Anmerkung B hat eine gerichtete Kante zu C, aber C ist in Q nicht vorhanden, daher geben wir die for-Schleife wieder nicht ein line16.

3.?

So erhalten wir die Entfernungen als

keine Veränderung Jungs

Beachten Sie, dass dies falsch ist, da der kürzeste Abstand von A nach C 5 + -10 = -5 beträgt, wenn Sie gehen a bis b bis c.

Für diesen Graphen berechnet der Dijkstra-Algorithmus fälschlicherweise den Abstand von A nach C.

Dies geschieht, weil der Dijkstra-Algorithmus nicht versucht, einen kürzeren Pfad zu Eckpunkten zu finden, die bereits aus Q extrahiert wurden .

Was die line16Schleife tut, ist, den Scheitelpunkt u zu nehmen und zu sagen: "Hey, es sieht so aus, als könnten wir von der Quelle über u zu v gehen . Ist diese (alternative oder alternative) Entfernung besser als die aktuelle Entfernung [v], die wir haben? Wenn ja, lassen Sie uns aktualisieren." dist [v] "

Beachten Sie, dass line16sie alle Nachbarn v (dh eine gerichtete Kante existiert von u nach v ) von u prüfen , die sich noch in Q befinden . In line14sie besuchten Notizen von Q. So entfernen , wenn x ein besuchtes Nachbar ist u , der Weg Quelle zu u zu xist nicht einmal in Betracht gezogen als möglicher kürzerer Weg von der Quelle zum v .

In unserem obigen Beispiel war C ein besuchter Nachbar von B, daher wurde der Pfad A bis B bis C.nicht berücksichtigt, so dass der aktuell kürzeste Pfad A bis C.unverändert blieb.

Dies ist tatsächlich nützlich, wenn die Kantengewichte alle positive Zahlen sind , da wir dann unsere Zeit nicht damit verschwenden würden, Pfade zu berücksichtigen, die nicht sein können kürzer sein können.

Ich sage also, dass es beim Ausführen dieses Algorithmus, wenn x vor y aus Q extrahiert wird , nicht möglich ist, einen Pfad zu finden - nicht möglichder kürzer ist. Lassen Sie mich dies anhand eines Beispiels erklären:

Da y gerade extrahiert wurde und x vor sich selbst extrahiert wurde, dann dist [y]> dist [x], da sonst y vor x extrahiert worden wäre . (line 13 min Entfernung zuerst)

Und da wir bereits angenommen haben, dass die Kantengewichte positiv sind, dh Länge (x, y)> 0 . Der alternative Abstand (alt) über y ist also immer größer, dh dist [y] + Länge (x, y)> dist [x] . Der Wert von dist [x] wäre also nicht aktualisiert worden, selbst wenn y als Pfad zu x betrachtet worden wäre. Daher schließen wir, dass es sinnvoll ist, nur Nachbarn von y zu berücksichtigen, die sich noch in Q befinden (Anmerkung in line16)

Diese Sache hängt jedoch von unserer Annahme einer positiven Kantenlänge ab. Wenn die Länge (u, v) <0 ist, können wir je nachdem, wie negativ diese Kante ist, den dist [x] nach dem Vergleich in ersetzen line18.

Daher ist jede dist [x] -Berechnung, die wir durchführen, falsch, wenn x entfernt wird, bevor alle Eckpunkte v - so dass x ein Nachbar von v ist, dessen negative Flanke sie verbindet - entfernt werden.

Weil jeder dieser v Eckpunkte der vorletzte Eckpunkt auf einem potenziellen "besseren" Pfad von der Quelle zu x ist , der vom Dijkstra-Algorithmus verworfen wird.

In dem Beispiel, das ich oben gegeben habe, war der Fehler, dass C entfernt wurde, bevor B entfernt wurde. Während dieses C ein Nachbar von B mit einer negativen Flanke war!

Zur Verdeutlichung sind B und C die Nachbarn von A. B hat einen einzelnen Nachbarn C und C hat keine Nachbarn. Länge (a, b) ist die Kantenlänge zwischen den Eckpunkten a und b.

Aditya P.
quelle
2
Wie Sie sagten, ist der bessere Weg, dies zu lösen, die Verwendung der heapq.heappush-Methode nach jedem Vergleich. Wir schieben die aktualisierte Entfernung in die Warteschlange zurück. Unter dieser Bedingung können die Dijkstra mit negativen Gewichten arbeiten. Ich habe es versucht, und das Ergebnis kam als 0,5, -5
Nosense
1
"Die Pfadquelle zu x zu u wird nicht einmal berücksichtigt"; Meinten Sie Quelle zu u zu x?
Slmatrix
1
@slmatrix danke, dass du das verstanden hast, ja, ich meinte, dass der Pfad von der Quelle zu u nach x ist, weil x ein Nachbar von u ist.
Aditya P
23

Der Dijkstra-Algorithmus geht davon aus, dass Pfade nur "schwerer" werden können. Wenn Sie also einen Pfad von A nach B mit einer Gewichtung von 3 und einen Pfad von A nach C mit einer Gewichtung von 3 haben, können Sie keine Kante und hinzufügen von A nach B bis C mit einem Gewicht von weniger als 3.

Diese Annahme macht den Algorithmus schneller als Algorithmen, die negative Gewichte berücksichtigen müssen.

zmbq
quelle
8

Richtigkeit des Dijkstra-Algorithmus:

Wir haben 2 Sätze von Eckpunkten in jedem Schritt des Algorithmus. Menge A besteht aus den Eckpunkten, zu denen wir die kürzesten Pfade berechnet haben. Satz B besteht aus den verbleibenden Eckpunkten.

Induktive Hypothese : Bei jedem Schritt wird davon ausgegangen, dass alle vorherigen Iterationen korrekt sind.

Induktiver Schritt : Wenn wir der Menge A einen Scheitelpunkt V hinzufügen und den Abstand auf dist [V] setzen, müssen wir beweisen, dass dieser Abstand optimal ist. Wenn dies nicht optimal ist, muss es einen anderen Pfad zum Scheitelpunkt V geben, der kürzer ist.

Angenommen, ein anderer Pfad führt durch einen Scheitelpunkt X.

Da nun dist [V] <= dist [X] ist, ist jeder andere Pfad zu V mindestens dist [V] lang, es sei denn, der Graph hat negative Kantenlängen.

Damit der Algorithmus von dijkstra funktioniert, dürfen die Kantengewichte nicht negativ sein.

Nikunj Banka
quelle
6

Probieren Sie den Dijkstra-Algorithmus in der folgenden Grafik aus, vorausgesetzt, es Ahandelt sich um den Quellknoten, um zu sehen, was passiert:

Graph

tb-
quelle
6
Entschuldigung, aber ich erhalte keine Fehlermeldung. Erster A->BWille 1und A->CWille 100. Dann B->Dwird 2. Dann C->Dwird -4900. Der Wert von Dwird also der -4900gleiche sein wie bei bellman-ford. Wie gibt das nicht die richtige Antwort?
Anirban Nag 'tintinmj'
9
@tintinmj Wenn Sie eine ausgehende Kante von D haben, wird diese besucht, bevor die Entfernung von D verringert wird, und daher nicht aktualisiert, nachdem sie entfernt wurde. Dies führt dann mit Sicherheit zu einem Fehler. Wenn Sie Ds 2 bereits nach dem Scannen ausgehender Kanten als endgültigen Abstand betrachten, führt selbst dieses Diagramm zu einem Fehler.
Christian Schnorr
@ tb- Tut mir leid, dass ich nach so langer Zeit gefragt habe, aber bin ich hier auf dem richtigen Weg? Zuerst A->Bwird 1und A->Cwird sein 100. Dann Bwird erforscht und setzt B->Dauf 2. Dann wird D untersucht, weil es derzeit den kürzesten Weg zurück zur Quelle hat? Werde ich richtig sein zu sagen , dass , wenn B->Dist 100, Cwurde zuerst untersucht habe? Ich verstehe alle anderen Beispiele außer Ihren.
Pejman Poh
@PejmanPoh Nach meinem Verständnis, wenn B-> D 100 war, da A-> C in der verwendeten HeapStructure höher ist, gibt der Extrakt min zuerst A-> C zurück, was bedeutet, dass der nächste gefundene kürzeste Pfad der Pfad ist nach C, danach wird der Weg von C-> D mit einem Gewicht von -5000 die offensichtliche Wahl sein, was uns zu dem Schluss führt, dass der kürzeste Weg von A-> C-> D sein würde, und ich bin mir ziemlich sicher, dass dies der Fall sein würde sei das normale Verhalten. Manchmal, wenn wir negative Zyklen haben, erhalten wir immer noch den richtigen Wert für den kürzesten Weg, aber definitiv nicht immer. Dies ist ein Beispiel, bei dem wir dies nicht tun werden.
T.Dimitrov
1

Denken Sie daran, dass im Dijkstra-Algorithmus, sobald ein Scheitelpunkt als "geschlossen" (und außerhalb der offenen Menge) markiert ist, davon ausgegangen wird , dass jeder von ihm ausgehende Knoten zu einer größeren Entfernung führt, sodass der Algorithmus den kürzesten Weg dorthin gefunden hat und dies auch tun wird Sie müssen diesen Knoten nie wieder entwickeln, dies gilt jedoch nicht für negative Gewichte.

Weinstock
quelle
0

Die anderen Antworten zeigen ziemlich gut, warum der Dijkstra-Algorithmus negative Gewichte auf Pfaden nicht verarbeiten kann.

Aber die Frage selbst basiert möglicherweise auf einem falschen Verständnis des Gewichts von Pfaden. Wenn negative Gewichtungen auf Pfaden in Pfadfindungsalgorithmen im Allgemeinen zulässig wären, würden Sie permanente Schleifen erhalten, die nicht aufhören würden.

Bedenken Sie:

A  <- 5 ->  B  <- (-1) ->  C <- 5 -> D

Was ist der optimale Weg zwischen A und D?

Jeder Pfadfindungsalgorithmus müsste kontinuierlich zwischen B und C wechseln, da dies das Gewicht des Gesamtpfads verringern würde. Wenn Sie also negative Gewichte für eine Verbindung zulassen, wird jeder Pfadfindungsalgorithmus möglicherweise in Frage gestellt, es sei denn, Sie beschränken die Verwendung jeder Verbindung nur einmal.

Dakkaron
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