 Djikstra vs Bellman-Ford |
chil14r
Grünschnabel
Dabei seit: 03.06.2008
Beiträge: 3
 |
|
Hallo Leute,
ein Fakt ist das Djikstra bei negativen Kantengewichten Probleme machen kann, also nicht die kürzesten Pfade korrekt berechnet.
Mein Problem: Dieses Manko ist mir nicht klar. Ich habe schon jede Menge Beispiele im internet angeschaut, aber meiner Meinung nach macht der Djikstra nichts verkehrtes..
Hier zum Beispiel
http://www.cs.princeton.edu/~wayne/kleinberg-tardos/06bellman-ford-2x2.pdf
Kann mir jemand das Problem erklären.
Danke!
|
|
05.04.2009 20:08 |
|
|
Ich
unregistriert
|
|
| RE: Djikstra vs Bellman-Ford |
     |
Soweit ich das sehe, würde Djikstra im Beispiel, über dem "Dijkstra. Can fail if negative edge costs." steht, schon korrekt funktionieren.
Betrachten wir aber beispielsweise folgenden Graphen:
(s) -> (u) Kosten 2
(s) -> (v) Kosten 1
(u) -> (v) Kosten -3
(v) -> (t) Kosten 2
(Bitte entschuldige die schlechte Formattierung.)
Nun wollen wir den kürzesten Weg von (s) nach (t) rausfinden. Dazu macht der Djikstra-Algo folgendes: Er Packt alle Nachbarn von (s) in die Queue und setzt deren Entfernungen und setzt (s) auf "erledigt".
Queue: (u,2), (v,1)
Es werden die Elemente in der Queue als (Knotenname, Entfernung) dargestellt.
Da nimmt er nun den Knoten mit der niedrigsten (bis dahin berechneten) Distanz raus: Das ist Knoten (v) mit Entfernung 1. (v) wird auf "erledigt" gesetzt. Dann schaut er sich dessen Nachbarn an, fügt sie - falls noch nicht "erledigt" - in die Queue, und setzt ihre Entfernungen:
Queue: (u,2),(t,3)
Nun wird der nächste Knoten aus der Queue entfernt: (u) mit Entfernung 2. Jetzt werden die Nachbarsentfernungen wieder aktualisiert. [b]Und jetzt kommt der Knackpunkt: [/b]Es kann jetzt zwar erkannt werden, dass man von (s) zu (v) noch günstiger kommt (nämlich mit Gesamtkosten -1 über (u)), aber da (v) bereits "erledigt", wird die Entfernung von (v) und erst recht nicht die Entfernungen, die von (v) ausgehen [b]nicht mehr erneuert. [/b]
Das Problem beim Dijkstra ist also, dass man bei negativen Kantengewichten durchaus in die Situation kommen kann, dass man bereits erledigte Knoten nachträglich noch günstiger erreichen kann, die Knoten aber bereits "erledigt" sind.
|
|
|
06.04.2009 19:50 |
|
|
chil14r
Grünschnabel
Dabei seit: 03.06.2008
Beiträge: 3
|
|
Hey Vielen Dank für dein Beispiel!
Jetzt seh ich es endlich ein 
Besten Gruß
|
|
|
06.04.2009 23:06 |
|
|
|
