Diskussion:Bellman-Ford-Algorithmus

Zum Archiv

Wie wird ein Archiv angelegt?

Automatische Archivierung

Auf dieser Seite werden Abschnitte halbmonatlich automatisch archiviert, wenn sie mit {{Erledigt|1=--~~~~}} markiert sind. Um die Diskussionsseite nicht komplett zu leeren, verbleibt mindestens ein Abschnitt.

Weblinks

Im Beispiel unter Ein anschauliches Beispiel wird doch nicht wirklich der Bellman-Ford-Algorithmus durchgeführt oder? Sieht für mich eher nach Djikstra aus.

--Derhman 16:01, 12. Aug 2006 (CET)

Also wenn ich mir den Weblink so ansehe, dann hast du auf jeden Fall recht. Ist in der Tat eher Dijkstra als Bellman-Ford. Auch wenn sie den Algorithmus selbst wirklich als Bellman-Ford darstellen... Aber wenn man sich mal deren Quellcode auf [1] ansieht, dann divergiert deren Algorithmus bei dem Beispiel a->b->a wobei alle Kantengewichte -1 sind. Bellman-Ford kann man auch bei negativen Kantengewichten verwenden, und in diesem Fall würde der Bellman-Ford Algorithmus (oder das was ich unter Bellman-Ford kenne) den negativen Zyklus erkennen. Deren Algorithmus erkennt ihn jedoch nicht, sondern schraubt die Distanzwerte ins unendliche... Werde den Link mal entfernen. Regnaron 20:15, 12. Aug 2006 (CEST)

Noch ein kleiner Nachtrag: Habe gerade gesehen, dass die Seite unter [2] einfach mal vorraussetzt, dass der Graph keine negativen Zyklen hat. Falls man in der Tat diese Annahme trifft, dann dürfte der Algorithmus wieder stimmen, und nicht so viel anderes machen als der hier beschriebene. Im hier beschriebenen Algorithmus werden in jedem Schritt *alle* Kanten relaxiert (geprüft ob ein kürzerer Pfad gefunden werden konnte), und in dem Algorithmus des Weblinks werden die Knoten extra noch einmal aufgeteit in solche deren Entfernung noch verkürzt werden kann (weil sie von einem Knoten ausgehen wessen Entfernung zum Startknoten gerade verinngert wurde), und solche die sich momentan eigentlich nicht ändern können. Würde trotzdem dafür plädieren den Weblink rauszulassen, da der Algorithmus erstens so wie er da steht eben nicht wirklich korrekt ist (negative Zyklen werden unnötigerweise ausgeschlossen), nicht wirklich ähnlich zu dem Algorithmus der hier beschrieben wird ist, und drittens ein IMHO sehr schlechtes Beispiel gewählt wird, da das besondere an Bellman-Ford ist, dass er eben auch auf mit negativen Kanten klarkommt, was aus dem Beispiel dort nicht ersichtlich wird. Und die Unterteilung der Knoten in verschiedene Klassen bringt asymtotisch gesehen auch keinen Laufzeitvorteil. Regnaron 20:35, 12. Aug 2006 (CEST)

OK! Verstanden. Dann wäre ich auch dafür den Link einfach zu entfernen. Das Applet ist weitaus aussagekräftiger. (aber leider auch nicht komplett richtig programmiert, gerade bei selbst entworfenen Graphen.) Derhman 21:08, 15. Aug 2006 (CEST)

Negative Zyklen: NP-Schwer

Die Behauptung, das Problem sei bei negativen Zyklen NP-Schwer ist so nicht haltbar.

Bellman-Ford arbeitet in einer Erweiterung auf Graphen mit negativen Zyklen korrekt und findet dort auch alle vorhandenen kürzesten Wege (bzw. kann ausgeben, dass es keinen kürzesten Weg gibt, falls dieser einen negativen Zyklus enthält und somit der kürzeste Weg unendlich viele Kanten enthält). Diese Erweiterung prüft einfach, welche Knotendistanzen sich nach n Relaxationsdurchläufen noch verringern und weiß nun, dass diese Knoten über einen negativen Zyklus erreichbar sind. Also werden alle diese Knoten und die davon erreichbaren Knoten auf Distanz minus unendlich gesetzt und für alle kürzesten Wege mit einem dieser Knoten als Ziel wird ausgegeben, dass es keinen endlichen kürzesten Weg gibt. Somit ist dieses Problem nicht NP-Schwer.

Das vermutlich gemeinte NP-Schwere Problem ist es, einfache kürzeste Wege zu finden - also kürzeste Wege, die jeden Knoten maximal einmal enthalten dürfen. In diesem Fall führen negative Zyklen nicht zu einer Distanz von minus Unendlich und es existieren auch für diese Knoten endliche kürzeste Wege - diese sind aber (Bei P!=NP) nicht polynomiell berechenbar, da sich Hamilton-Path darauf reduzieren lässt. (nicht signierter Beitrag von 141.3.208.77 (Diskussion) 12:33, 22. Feb. 2011 (CET))

Hallo! Gemäß Definition eines Weges aus dem Korte-Vygen darf ein Weg jeden Knoten höchstens einmal erreichen. MfG Stefan Knauf 01:35, 24. Feb. 2011 (CET)

Meines Wissens nach entspricht diese Einschränkung der Definition eines Pfades. Ein Weg darf durchaus mehrfach den selben Knoten enthalten. Lg Sebastian (nicht signierter Beitrag von 141.3.209.109 (Diskussion) 11:37, 24. Feb. 2011 (CET))

Man kann das ganze ja nach Wikipediadefinition umschreiben. Also beispielsweise: "Falls es negative Kreise gibt, ist das finden von kürzesten einfachen Wegen (Pfaden) NP-schwer, folglich findet kein bekannter polynomieller Algorithmus (wie der von Bellman und Ford) zu jedem Knoten den kürzesten Pfad. Es ist jedoch möglich, mit dem Algorithmus das Vorhandensein von Kreisen negativen Gewichtes zu erkennen, somit kann er mit einer Modifikation kürzeste Wege finden, wenn nicht gefordert ist, dass sie einfach sind." Soweit mein Vorschlag, wer will, kann es ja so oder ähnlich einfügen. Lg --Star Flyer 00:52, 25. Feb. 2011 (CET)

IP 141.3.208.77 hat absolut Recht und die Sachlage umfassend und korrekt dargestellt. Das Standardwerk zu Algorithmen ist wohl der Wälzer von Cormen, Leiserson, Rivest und Stein - da steht es genauso, einschließlich ausführliches Beispiel. Zudem ist das Finden der negativen Zykel wohl die wichtigste Rechtfertigung dafür, dass dieser lahme Algorithmus heute immer noch von Interesse ist (über die Historie hinaus). Ich werde das demzufolge jetzt wieder ändern - so wie es vor Jahren hier schonmal korrekt stand. --Graf Alge 20:50, 1. Mai 2011 (CEST)

Visualisierung

Hallo,

ich überlege gerade, wie ich den Bellman-Ford-Algorithmus am geschicktesten visualisiere. Ich würde eine Animation in dieser Art machen:

Ich würde in diesem Graphen bei "a" anfangen. Gibt es Vorschläge für einen besseren Beispielgraphen? --Martin Thoma 15:25, 20. Jul. 2012 (CEST)

Auf der Seite gibt es kein richtiges Bildmaterial, dass einen Leser weiter helfen würde. Diese Animation aber erfüllt schon so einiges. Wäre jemand da, der das einbinden könnte? 178.4.180.128 13:33, 24. Okt. 2015 (CEST)

Kreis = Zyklus

Warum ist im Artikel immer von "Kreisen" die Rede? Ist das Fachwort für einen "Kreis" im Graphen nicht Zyklus? ––P.Mullan (Diskussion) 08:14, 22. Aug. 2013 (CEST)