Diskussion:Algorithmus von Floyd und Warshall
aus Wikipedia, der freien Enzyklopädie
Korrektur: Warshall-Algorithmus liefert in der angegebenen Form die transitive Hülle, nicht die "reflexive, transitive Hülle" (dafür müsste man die Diagonale auf 1 setzen). HS, 2006-10-03
laufzeit beim ersten alg. ist n hoch 4 wegen min.
- Minimum zweier Zahlen hat Komplexität O(1) ==> Komplexität bleibt bei O(n^3) --Mulno 16:06, 25. Mai 2005 (CEST)
-
- es kann irgendwas nicht stimmen, da paarweglänge nur in O(n^4) mgl., trans. hülle ist in O(n^3) mgl.--141.35.17.32 20:56, 25. Mai 2005 (CEST)
- Sagt wer? In meinen Unterlagen steht, beide haben gleiche Komplexität. Für dünne Graphen und effizientere Datenstrukturen ist die Komplexität natürlich O(|E| x |V|).
- -- Mulno 00:18, 26. Mai 2005 (CEST)
- es kann irgendwas nicht stimmen, da paarweglänge nur in O(n^4) mgl., trans. hülle ist in O(n^3) mgl.--141.35.17.32 20:56, 25. Mai 2005 (CEST)
-
-
-
- Ich hab fälschlicherweise an die Anzahl von Paarwegen gedacht (in O(n^4) mgl.), so stimmts aber laufzeitmässig. --141.35.17.32 19:28, 14. Jun 2005 (CEST)
-
-
Das zugehörige Problem zum Algorithmus
- sollte man nicht vielleicht noch in den Artikel aufnehmen, dass der Alg. von Floyd eine Lösung des APSP (all-pairs-shortest-paths-) Problems darstellt? gut, ist nur die englische beschreibung dessen, was da schon steht, aber so heißt das Problem dazu nunmal :-)
