Bellmann-Ford
-
hallo,
ich bin auf der Suche nach einer Anleitung für den Bellmann-Ford Algorithmus für den kürzesten Pfad zwischen 2 Punkten im Graphen mit negativer Kanten Gewichtung(für Dummies).
Was ist der Unterschied zu Dijkstra?
Ich war schon auf verschiedenen Seiten im Web (u.a http://www.mcgods.de/fun/1904/node8.html), konnte dies aber nicht so richtig Nahvollziehen…
hat jemand zufällig ein Skript oder einen Link dazu?Danke
-
Der Dijkstra Algo ist hier zu finden:
http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D196288&p=274mehr kann ich dazu leider nicht beitragen
-
Was ist der Unterschied zu Dijkstra?
der Dijkstra Algo hat mit negativen Gewichtungen Probleme - das ist bestimmt schon mal ein Unterschied
-
Jo, der Dijkstra weiß, daß wenn ein Weg zu einem Punkt x länger ist als zum Punkt y , dann kann man nicht von y noch weiterlaufen bis x und dann nen kürzeren Weg haben.
Man sieht das schon, wenn man mal ein Dreieck nimmt.
Stellen wir es mal auf den Kopf. An dem Punkt unten starten wir.Von dort aus gibt es Kanten nach links und rechts oben.
Die Links soll mal 100 Kosten, die nach rechts 1000.
Dann nehmen wir noch ne Kante von rechts oben nach links oben mit Kosten -999 dazu.Der Dijkstra würde direkt den günstigsten Weg ab Anfang nehmen. Damit kommt er mit Kosten 100 zum linken oberen Knoten. Das kann auch nie besser werden, weil seiner Ansicht nach ja alle etwas kosten und er den kürzesten genommen hat.
Der andere müßte da wohl auch erstmal lang, würde aber, wenn er dann den anderen Weg anschaut einen kürzeren entdecken und müßte das dann entsprechend updaten.
MfG Jester
-
Jo, der Dijkstra weiß, daß wenn ein Weg zu einem Punkt x länger ist als zum Punkt y , dann kann man nicht von y noch weiterlaufen bis x und dann nen kürzeren Weg haben.
außerdem wäre es vielleicht sinnvoll einen weg mit negativen kosten möglichst häufig zu druchlaufen um die gesamtkosten zu senken
-
Vertexwahn schrieb:
außerdem wäre es vielleicht sinnvoll einen weg mit negativen kosten möglichst häufig zu druchlaufen um die gesamtkosten zu senken
Wenn man es aber einen Rundweg zu finden, der den Pfad benutzt und negative Kosten hat, dann kann man das unendlich oft tun. Also sollte der Graph sowas nicht zulassen, weil's sonst keinen Sinn mehr macht.
Damit wissen wir schonmal, daß es nicht lohnt so nen Pfad mehrfach zu benutzen.
-
Es darf schon Zykel mit negativen Gesamtkosten geben. Der Zielknoten darf nur nicht von den Zykelknoten aus erreichbar sein.
-
ok, soweit ich das jetzt herausgefunden habe, liegt der Unterschied darin, dass Dijkstra einmal gefundene Knoten nicht mehr kontrolliert, ob es einen kürzeren Pfad gibt. Bellmann-Ford tut dies aber... ??? (bin mir aber nicht sicher)
-
Ponto schrieb:
Es darf schon Zykel mit negativen Gesamtkosten geben. Der Zielknoten darf nur nicht von den Zykelknoten aus erreichbar sein.
Okay, das stimmt. Das ändert aber nix dran, daß es sich nicht lohnt Kanten mehrfach zu benutzen. Damit verhindern wir auch gleich, daß wir in solchen Zykeln hängenbleiben.
-
Ich würde mal den Algorithmus in einem guten Buch nachschlagen. Hier mal Vorschläge:
Combinatorial Optimization (Korte, Vygen, Springer Verlag, 2000, Seite 142f)
Introduction to Algorithms (Cormen, Leiserson, Rivest, MIT Press, 1990, Seiten 532-535)Die Originalartikel sind:
Bellman, R.E.: On a routing problem. Quarterly of Applied Mathematics 16 (1958), Seiten 87-90
Ford, L.R.: Network flow theory. Paper P-923, The Rand Corporation, Santa Monica 1956
Moore, E.F.: The shortest path through a maze. Proceedings of the International Symposium on the Theory of Switching, Part II, Harward University Press, 1959, Seiten 285-292
-
Kann mir jemand erklären was "Kanten mit nagtivem Gewicht sind tolerierbar, solange keine vom Quellknoten errichbare Zyklen negativer Länge entstehen." heisst? Vielleicht mit einem kleinen Beispiel?
Dankeschön.
-
Angenommen es gäbe nen Zyklus mit negativer Länge. Dann könnte man den ja immer im Kreis laufen und der Weg würde immer kürzer. Wenn die kürzester Pfad-Suche vom Startknoten aus da jetzt hingelangen würde, würde sie ja dort hängen bleiben und unendlich lange dort im Kreis laufen (davon wird der Weg ja soooooo kurz). Wir hätten also ne endlosschleife. Wenn man allerdings vom Startknoten nicht zum dem Zyklus hinlatschen kann, dann kann man auch nicht drin hängen bleiben.
MfG Jester
-
Jester schrieb:
Angenommen es gäbe nen Zyklus mit negativer Länge. Dann könnte man den ja immer im Kreis laufen und der Weg würde immer kürzer. Wenn die kürzester Pfad-Suche vom Startknoten aus da jetzt hingelangen würde, würde sie ja dort hängen bleiben und unendlich lange dort im Kreis laufen (davon wird der Weg ja soooooo kurz). Wir hätten also ne endlosschleife. Wenn man allerdings vom Startknoten nicht zum dem Zyklus hinlatschen kann, dann kann man auch nicht drin hängen bleiben.
MfG Jester
Cool habs verstanden, dankeschön Jester
.