Bellman-Ford: Rückgabe ist "all pairs" oder "von einem Knoten"?

goerlibe
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:22

Bellman-Ford: Rückgabe ist "all pairs" oder "von einem Knoten"?

Beitrag von goerlibe » 16. Jul 2017 15:11

In der Vorlesung und auch auf Nabla wurde ein Algorithmus zur Bestimmung der kürzesten Wege von allen Knoten zu allen anderen Knoten (all pairs shortest paths) unter dem Namen Bellman-Ford vorgestellt.
Als ich diesen nicht gleich verstanden habe, habe ich im Internet nach dem Bellman-Ford Algorithmus gesucht, jedoch wird dort meist ein Algorithmus vorgestellt, der die kürzesten Wege von einem bestimmten Knoten aus berechnet, und nicht all-pairs.

Wie kommt es zu den geschilderten Unterschieden? Gibt es da mehrere Algorithmen unter dem gleichen Namen? Oder ist der Algorithmus der Vorlesung eine Abwandlung?

OAEP
Neuling
Neuling
Beiträge: 4
Registriert: 31. Mai 2017 15:50

Re: Bellman-Ford: Rückgabe ist "all pairs" oder "von einem Knoten"?

Beitrag von OAEP » 17. Jul 2017 18:26

Bellman-Ford kannst du von einem Knoten aus ausführen oder aber von allen, die Idee/Invariante ist immer das gleiche, daher ist beides auch "Bellman-Ford".
- In der Grundform ist Bellman-Ford von einem Knoten ausgehend (in O(|V|^3))
- Für alle Knoten einmal anwenden: Zack, hast du deinen All-Pairs-Algorithmus (in O(|V|^4))
Warum Prof. Weihe die All-Pairs Variante gezeigt hat, ist folgendes: Die Summen-Maximierungsbildung auf der Matrix ist ein Ring! Daher kann man mit Repeated-Squaring tricksen und bekommt damit bei All-Pairs-Verwendung doch noch O(|V|^3 * log|V|). Die Invariante im Wortlaut ändert sich dadurch geringfügig, allerdings nennt man das immer noch "Bellman-Ford".

Weiterführend:
Floyd-Warshall hingegen ist allein von der Idee her ein All-Pairs Algorithmus und das sogar in O(|V|^3)

Antworten

Zurück zu „Archiv“