Diskussion:Bellman-Ford-Algorithmus/Archiv
Diskussion zum Algorithmus
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"
- Der Algorithmus unterscheidet sich von dem im englischen Wiki. Welcher ist der richtige?
- In Zeile 08 : Ist das u identisch mit dem aus Zeile 06? Könnte man meiner Meinung nach auch als Neubinden lesen.
- 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
- Zeile 12 muss wohl U := U + {v} heißen?
--Mulno 16:44, 14. Mai 2005 (CEST)
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)
- 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)
- Hab folgendes verändert:
Kreise --> Zyklen Kosten --> Gewicht Pfad --> Weg
- 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)
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)
- Die Laufzeitkomplexität ist in . Das wurde offensichtlich schon nachgetragen. Damit dürfte auch diese Diskussion beendet sein.
Algo komplett falsch!!!
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)
Beispiel
Ich finde, ein anschauliches Beispiel würde ganz gut in den Artikel passen. --Daniel Mex 17:27, 3. Jul. 2007 (CEST)
- Ich habe es zur Kenntnis genommen. Unter "Visualisierung" kannst du ja mitdiskutieren, ob das Beispiel gut gewählt ist. --Martin Thoma 15:31, 20. Jul. 2012 (CEST)
Kürzeste Wege mit maximal k Kanten
Leute, der am 7.Juni sichtbare Algorithmus berechnet zwar den kürzesten Weg, aber die Erklärung darunter ist komplett falsch, da der angeführte Algorithmus nicht im k-ten Durchlauf einen Weg mit maximal k Kanten zu jedem Knoten berechnet.... und ja, ich habe es implementiert, so wie es hier angeführt war/ist. Werde jetzt den Algorithmus ändern, sodass die Erklärung stimmt. --Madpower 12:26, 7. Jun. 2011 (CEST)
- Hallo Madpower! Mit Deinem Kritikpunkt hast Du vollkommen Recht. Aber von Deiner Verbesserung des Algorithmus bin ich nicht so überzeugt. Deswegen habe ich wieder die alte Version eingefügt und einfach das komplett falsche Zeug darunter berichtigt. Da die von Dir eingefügte neue Menge F keine Teilmenge der Kantenmenge sein musste, wüsste ich nicht, wie der Algorithmus in Deiner Version gemeint gewesen wäre. MfG Stefan Knauf 23:16, 7. Jun. 2011 (CEST)