Unterschied: Ford - Bellmann

WiWi_Master · 13 September 2012

Es geht um kürzeste Wege Algorithmen.

Wo ist bei der Vorgehensweise der Unterscheid zwischen Ford und Bellmann. Das die Voraussetzungen etwas verschieden sind weiß ich, aber irgendwie wirkt die Vorgehensweise zur Bestimmung der kürzesten Wege für mich bei beiden gleich. Den Dikjstra habe ich hingegen verstanden.

Sus_Scrofa · 13 September 2012

Bellman ---> nur für zyklenfreie Netzwerke / kürzeste Wege von einem Startknoten

Ford & Fulkinson ---> damit sind die Probleme lösbar, die sich a.) als Graphen beschreiben lassen und b.) auch Zyklen enthalten können. S. auch Bsp. 4.5 auf der S.81

WiWi_Master · 14 September 2012

Danke für die Info.

Welche die Voraussetzungen sind, ist mir bewusst. Mir geht es jedoch um den Algorithmus an sich. Wie geht man genau vor? Da sind Bellmann und Ford für mich irgendwie gleich.

Sus_Scrofa · 14 September 2012

Ach so ---> Du meinst Bellman vs. Ford (= und nicht F&F). Ja, eine berechtigte Frage…

Ich glaube, der Unterschied liegt im Rechenaufwand / Zeitkomplexität ---> bei Bellman = O(n^2), bei Ford = O(n^3), aber das ist je nicht klausurrelevant

Ansonsten denke ich, dass die zwei Verfahren sich tatsächlich im Sinne der Anwendbarkeit unterscheiden, d.h. Zyklen oder keine Zyklen…

Ich habe den Unterschied auch so verstanden, dass wir bei Bellman zunächst topologisch sortieren sollen und immer den nächsten kürzesten Knoten zu unserer – vorher berechneten – kürzesten Distanz dazu addieren.
Bei Ford dagegen betrachten wir irgendwie nur die Nachfolger und die „abgearbeiteten“ Nachfolger aus der M-Liste (= S.59) wegnehmen und zu unserem kürzesten Weg dazu addieren…

Der Unterschied wäre quasi nur in der Vorgehensweise, meine ich…
…aber mehr fällt mir auch nichts ein… 🙁

Unterschied: Ford - Bellmann

Thema 'Termine Modul 32831 Elemente der Finanzwirtschaft'

Thema 'Termine Modul 32791 Dienstleistungsmanagement – Kundenbeziehungsmanagement'

Thema 'Termine Modul 32781 Rechnungslegung'

Thema 'Termine Modul 32771 Internationale Finanzwissenschaft und Umweltökonomie'

Thema 'Termine Modul 32751 Konstruktion und Analyse ökonomischer Modelle'

WiWi_Master

Sus_Scrofa

WiWi_Master

Sus_Scrofa

Weiter lesen