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

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.

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.

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

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

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

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.

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.

Schließlich extrahieren wir B, wonach . 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.

So erhalten wir die Entfernungen als

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

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 ist 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 nicht berücksichtigt, so dass der aktuell kürzeste Pfad 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 - der 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.

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.

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.

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

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.

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.

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.