Komplexität All pair shortest paths

Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
marlonmalter
Neuling
Neuling
Beiträge: 2
Registriert: 4. Jul 2016 12:52

Komplexität All pair shortest paths

Beitrag von marlonmalter » 4. Jul 2016 13:52

Hallo,
bei dem algorithmischen Problem All pair shortest paths ist ja die Komplexität für Bellman-Ford als Theta n^4 angegeben und für Floyd-Warshall als Omega n^3. Für die Berechnung einer Distanz für einen Matrixeintrag ist bei BF angegeben: "Computing one update value requires Theta(n) steps)".
Und für FW: "Each update requires a constant number of steps". Worin genau besteht die Verbesserung(oder was ist der Unterschied) bei FW, sodass dieser Algorithmus dort nur noch einen konstanten Aufwand hat? Es könnte ja auch bis zu n mögliche Kombinationen für die Berechnung pro Länge geben, da man es ja auch jeweils mit bis zu n Zwischenknoten probieren muss?!

Vielen Dank
Marlon
Zuletzt geändert von marlonmalter am 4. Jul 2016 20:06, insgesamt 1-mal geändert.

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Komplexität All pair shortest paths

Beitrag von Prof. Karsten Weihe » 4. Jul 2016 15:17

marlonmalter hat geschrieben:Worin genau besteht die Verbesserung(oder was ist der Unterschied) bei FW sodass dieser Algorithmus dort nur noch einen konstanten Aufwand hat? Es könnte ja auch bis zu n mögliche Kombinationen für die Berechnung pro Länge geben, da man es ja auch jeweils mit bis zu n Zwischenknoten probieren muss?!
Der Witz bei Floyd-Warshall ist, dass Sie diese ganzen verschiedenen Fälle nicht der Reihe nach durchgehen müssen wie bei Bellman-Ford, sondern Sie finden die beste Option schon in der Matrix vor, die in der vorhergehenden Iteration berechnet wurde. Bei Bellman-Ford ist das leider nicht der Fall, da muss die beste Option wirklich in \(\Theta(n)\) erst herausgesucht werden.

Was ist der beste Pfad von \(v\) nach \(w\) unter der einschränkenden Voraussetzung, dass alle Zwischenknoten aus \(\{v_1,\ldots,v_k\}\) sind? Es gibt zwei Möglichkeiten: Entweder ist \(v_k\) in diesem Pfad enthalten oder nicht. Falls nicht, ist der beste Pfad mit Zwischenknoten aus \(\{v_1,\ldots,v_{k-1},v_k\}\) identisch mit dem besten Pfad mit Zwischenknoten aus \(\{v_1,\ldots,v_{k-1}\}\). Und dieser Pfad ist schon in früheren Iterationen berücksichtigt worden, ist also der Eintrag \((v,w)\) in der Matrix aus der letzten Iteration. Falls hingegen \(v_k\) in diesem besten Pfad enthalten ist, dann wissen wir genau, wie dieser Pfad aussieht: der beste Pfad von \(v\) nach \(v_k\) mit Zwischenknoten aus \(\{v_1,\ldots,v_{k-1}\}\) und der beste Pfad von \(v_k\) nach \(w\) mit Zwischenknoten aus \(\{v_1,\ldots,v_{k-1}\}\). Beides findet sich in der Matrix aus der letzten Iteration.

Man kann also etwas flapsig sagen, Floyd-Warshall ist deshalb asymptotisch schneller als Bellman-Ford, weil bei der Vorgehensweise von Floyd-Warshall die iterative Datenorganisation besser zusammenpasst als bei Bellman-Ford.

Zur sprachlichen Vereinfachung habe ich jetzt ausgelassen, dass es auch mehrere beste Pfade geben kann.

Klarer geworden?

KW

marlonmalter
Neuling
Neuling
Beiträge: 2
Registriert: 4. Jul 2016 12:52

Re: Komplexität All pair shortest paths

Beitrag von marlonmalter » 4. Jul 2016 17:35

Jetzt habe ich es verstanden, vielen Dank!

Antworten

Zurück zu „AuD: Vorlesung“