Diskussion:Bellman-Ford-Algorithmus

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)

01 für jedes v aus V
02 Distanz(v) := unendlich, Vorgänger(v) := kein
03 Distanz(s) := 0, Vorgänger(s) := s, U := V
04
05 solange U nicht leer
06 wähle u aus U
07 U := U - {u} 
08 für jedes (u,v) aus E wiederhole V-mal
09 wenn Distanz(u) + Kosten(u,v) < Distanz(v) dann
10 Distanz(v) := Distanz(u) + Kosten(u,v)
11 Vorgänger(v) := u
12 U := U - {v}
13 für jedes (u,v) aus E'
14 wenn Distanz(u) + Kosten(u,v) < Distanz(v) dann
15 STOP mit Ausgabe "Kreis negativer Länge gefunden"

1. Der Algorithmus unterscheidet sich von dem im englischen Wiki. Welcher ist der richtige?
2. In Zeile 08 : Ist das u identisch mit dem aus Zeile 06? Könnte man meiner Meinung nach auch als Neubinden lesen.
3. Schleife 08-12 : Wird V-mal das selbe wiederholt? Es ändert sich doch ab dem zweiten Mal nichts mehr? Und ist mit V |V| gemeint?

1. ja 2. weil der längste Weg |V| lang sein kann und evtl. in 13-15 als neg. kreis erkannt wird. 3. ja -mfg

1. Zeile 12 muss wohl U := U + {v} heißen?

--Mulno 16:44, 14. Mai 2005 (CEST) Beantworten

Habe den Artikel inzwischen überarbeitet und denke der Algorithmus ist so korrekt. Bin aber trotzdem noch nicht zufrieden. Insbesondere findet man in manchen Referenzen auch den Namen Moore! -- Mulno 16:14, 25. Mai 2005 (CEST) Beantworten

Ich habe ihn auch als Moore-Bellman-Ford-Algorithmus kennen gelernt (Korte/Vygen), aber der Google-Test legt nahe, dass er als Bellman-Ford-Algorithmus wohl deutlich verbreiteter ist. Moore hat wohl 1959 noch etwas beigetragen. -- DasJan 15:10, 18. Feb 2006 (CET)

1. Hab folgendes verändert:

Kreise --> Zyklen Kosten --> Gewicht Pfad --> Weg

1. Folgendes muss meiner Meinung noch verändert werden:

- Konsitenz in dem gebrauchten Vokabular durch den ganzen Artikel, d.h. nur Pfad, oder nur Weg benutzen; (Kreis / Zyklus) usw. - Der Einschub über den Algorithmus von Dijkstra sollte zum Schluss gebracht werden und es sollte nur der Unterschied zum Bellman-Ford Algor. präzise formuliert werden, also nicht näher auf den eigentlichen Dijkstra - Algo. eingegangen werden, da es ja einen eigenen Artikel hierfür gibt.

Ich habe diesen Artikel im Portal Mathematik als überarbeitungswürdig eingetragen. Vielleicht erbarmt sich ja jemand. --ercas ^✉ 19:02, 27. Aug 2005 (CEST)

Pfade und Wege sind auf gerichteten Graphen etwas unterschiedliches, ebenso Zyklen und Kreise.

In Wege, Pfade, Zyklen und Kreise in Graphen ist Weg ein Oberbegriff für die drei anderen Begriffe. Pfade sind Wege ohne Schlaufen, Zyklen sind Wege, bei denen Start- und Endknoten identisch sind (aber auch weitere Knoten dürfen identisch sein), und Kreise sind einfache Zyklen (bei denen nur Start- und Endknoten identisch sind).

Ich bin zwar auch nicht ganz zufrieden mit der dortigen Definition (und ich bin nicht allein damit, siehe dortige Diskussion), aber ich werde sie schnell mal einarbeiten.

92.227.69.242 11:23, 15. Aug. 2008 (CEST) Beantworten

Vermissen tue ich auch eine Info über die Komplexität des Algorithmus. Diese Info fehlt übrigens bei fast allen Graphentheoretischen Algorithmen. (Der vorstehende, nicht signierte Beitrag – siehe dazu Hilfe:Signatur – stammt von 213.47.207.78 (Diskussion • Beiträge) 20:26, 19. Okt. 2005)

Also dieser Algorithmus ist einfach nur falsch!!!

Wenn ich ihn ansehe, dann berechnet dieser den minimal spannenden Baum des Graphen und gibt dann (eventuell korrekt) aus ob dieser überhaupt existieren kann.

Kürzeste Wege berechnet er sicherlich nicht! Das sieht man bereits daran, daß er den Startknoten s garnicht benötigt..

Wenn ich Zeit finde die nächsten Tage werde ich ihn korrigieren.

Grundgedanke: Der Algorithmus läuft in n=|V| Phasen ab. In jeder Phase werden alle Distanzen zu den direkten Nachbarn aller Knoten der letzten Phase berechnet. Sind nach n Phasen noch Knoten in der Queue, so existiert mindestens ein Zyklus negativer Länge. Diesen kann man dann mittels einfacher Tiefensuche zurückverfolgen.

Die Komplexität ist somit schlichtweg O(|V|*|E|), also O(|V|^3). (Im worstcase wird in jeder Phase kann jeder Knoten besucht)

Nein, der Algorithmus ist nicht falsch. Die Vorgänger-Funktion gibt am Ende an, über welche Kante man jeweils auf dem kürzesten Weg zu s kommt, die Distanz-Funktion wie lang dieser Weg ist. Noch ein Tipp: wenn man seine Beiträge signiert und weniger Ausrufezeichen verwendet stößt man hier im Allgemeinen auf mehr Diskussionsfreudigkeit. --DasJan 14:51, 18. Feb 2006 (CET)

Ich finde, ein anschauliches Beispiel würde ganz gut in den Artikel passen. --Daniel Mex 17:27, 3. Jul. 2007 (CEST) Beantworten

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)) Beantworten

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) Beantworten

Meines Wissens nach entspricht diese Einschränkung der Definition eines Pfades. Ein Weg darf durchaus mehrfach den selben Knoten enthalten. Lg Sebastian