[SIZE=4][FONT=arial]Es geht um kürzeste Wege Algorithmen.[/FONT][/SIZE]
[SIZE=4][FONT=arial]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.[/FONT][/SIZE]
Comments
Sus_Scrofa
Contributions on this page: 1
[SIZE=4][FONT=Times New Roman][COLOR=black]Bellman ---> nur für zyklenfreie Netzwerke / kürzeste Wege von [U]einem[/U] Startknoten[/COLOR][/FONT][/SIZE]
[SIZE=4][FONT=Times New Roman][COLOR=black]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[/COLOR][/FONT][/SIZE]
WiWi_Master
Contributions on this page: 2
View profileDanke 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
Contributions on this page: 1
[SIZE=4][FONT=Times New Roman]Ach so ---> Du meinst Bellman vs. Ford (= und nicht F&F). [/FONT][FONT=Times New Roman]Ja, eine berechtigte Frage…[/FONT][/SIZE]
[SIZE=4][FONT=Times New Roman]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[/FONT][/SIZE]
[SIZE=4][FONT=Times New Roman]Ansonsten denke ich, dass die zwei Verfahren sich tatsächlich im Sinne der Anwendbarkeit unterscheiden, d.h. Zyklen oder keine Zyklen…[/FONT][/SIZE]
[SIZE=4][FONT=Times New Roman]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. [/FONT][/SIZE]
[SIZE=4][FONT=Times New Roman]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…[/FONT][/SIZE]
[SIZE=4][FONT=Times New Roman]Der Unterschied wäre quasi nur in der Vorgehensweise, meine ich…[/FONT][/SIZE]
[SIZE=4][FONT=Times New Roman]…aber mehr fällt mir auch nichts ein… :( [/FONT][/SIZE]