Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Algorithmus von Floyd: Aufwand unter Berücksichtigung der billigsten Pfade
In den MCs der WS12 Klausur wird folgendes gefragt:
“Wenn man beim Algorithmus von Floyd nicht nur die Länge der kürzesten Pfade bestimmt, sondern auch alle billigsten Pfade, ist sein Aufwand…”
Laut FSI-Lösung ist Θ(n³) die richtige Lösung:
Der Aufwand für Floyd beträgt Θ(n³). Den kürzesten Pfad zwischen zwei Knoten kann man in Θ(m) finden, wobei m die Länge dieses Pfades ist.
Nachdem ein Pfad von v nach u höchstens die Länge n haben kann, Pfade in die Rückrichtung von u nach v nicht zwangsläufig die gleiche Länge haben müssen und es n Knoten gibt,
lautet die worst-case Abschätzung: O(n²)
Insgesamt gilt jedoch: Θ(n³) + O(n²) = Θ(n³)
Woher kommt denn das Θ(n³)? in der Erklärung ist für mich nur ersichtlich, dass das O(n²) aus n(hinweg)*n(Rückweg) entsteht.
Liebe Grüße
Speedy
Ohne Aufgabe zu kennen: Floyd hat 3x Schleife über alle Knoten → n³
Danke 