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 2
ist 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
Antworten:
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:
Angenommen, die Kanten sind wie in Ihrem Beispiel von links nach rechts gerichtet.
Ihr Algorithmus funktioniert wie folgt:
d(A)
aufzero
und die anderen Distanzeninfinity
.A
und setzend(B)
auf1
,d(C)
aufzero
undd(D)
auf99
.C
ohne Nettoänderungen.B
, was keine Auswirkung hat.D
, welche Änderungend(B)
zu-201
.Beachten Sie jedoch, dass dies am Ende
d(C)
immer noch der Fall ist0
, obwohl der kürzeste WegC
Lä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 gelangenA
, würden Sie am Ende den falschen Pfad vonC
nach zurück nehmenA
.quelle
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.
quelle
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.
quelle
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.
quelle
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.
for
Schleife zum Entspannen von Scheitelpunkten. Dies ist der einfachste Weg, um den Dijkstra-Algorithmus zu implementieren. Die zeitliche Komplexität ist O (V ^ 2).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):
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.
quelle
Ü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.
quelle
"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.
quelle
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.
quelle