Seite 1 von 1

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

Verfasst: 16. Jul 2017 15:11
von goerlibe
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?

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

Verfasst: 17. Jul 2017 18:26
von OAEP
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)