Diskussion:Algorithmus von Floyd und Warshall

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

2. Satz des Artikels

"Er findet die Länge der kürzesten Wege zwischen allen Paaren von Knoten eines gewichteten Graphen (engl. All Pairs Shortest Path Problem = APSP, oder auch: All Pairs Best Path Problem = APBP) in der Version Floyds oder die transitive Hülle eines Graphen in der Version Warshalls."

--Die Klammer stört den Lesefluss erheblich. Ih bin dafür den Satz neu zu formulieren. (nicht signierter Beitrag von 141.84.9.33 (Diskussion | Beiträge) 15:28, 10. Apr. 2010 (CEST)) [Beantworten]

Ich glaube der Warshall-Algorithmus funktioniert so nicht: Vorschlag: 

 FOR k := 1 TO n DO
   FOR i := 1 TO n DO
     IF A[i; k] = 1 THEN
       FOR j := 1 TO n DO
         IF A[k; j] = 1 THEN A[i; j] = 1

SK,2007-05-31

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)[Beantworten]
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)[Beantworten]
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)[Beantworten]
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 :-)
Bei der Erklärung zum Floyd-Algo ist einmal von w und einmal von k die Rede, dabei ist das dasselbe. Außerdem wird n nicht definiert.
Die Variablenzuweisung ist in diesem Artikel tatsächlich mangelhaft. k wur dzunächst richtig als Bezeichnung des Index genutz, dann jedoch als Bezeichnung Knotenpunktes w. Im weiteren wird w auch noch als Name für die ganze Matrix genutzt.

--Teurox 18:22, 27. Apr. 2011 (CEST)[Beantworten]

Warshall Algorithmus korrekt?[Quelltext bearbeiten]

Hi,

der Algorithmus sucht für eine gegebene Relation nach Lücken in der Transitivität und füllt diese. Dadurch kommen neue Punkte hinzu. Diese Punkte müssten doch auch noch einmal im Hinblick auf die Transitivität geprüft werden, da diese Punkte auch genutzt werden können um einen entfernten Punkt zu erreichen, welcher u.U. dann nicht erreichbar ist.

--Seppman86 (17:02, 27. Mai 2013 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)[Beantworten]

Platzbedarf fehlt[Quelltext bearbeiten]

Platzbedarf $\Theta(|V|^2)$ oder n^2 fehlt hier bzw. das Eingehen auf den Platzbedarf (nicht signierter Beitrag von 134.61.137.104 (Diskussion) 15:20, 24. Jul 2015 (CEST))

Warshall-Algorithmus[Quelltext bearbeiten]

Sollte nicht die Initialisierung von d mit den Werten aus w auch bei Warshall erfolgen? Sonst wird da nicht viel berechnet. (nicht signierter Beitrag von 129.69.226.21 (Diskussion) 17:29, 11. Aug. 2016 (CEST))[Beantworten]

Ja. Ich stimme zu. --H.Marxen (Diskussion) 18:55, 12. Aug. 2016 (CEST)[Beantworten]
Ich stimme ebenfalls zu.--Doktor Wu (Diskussion) 09:43, 5. Jun. 2020 (CEST)[Beantworten]

Distanzmatrix im Beispiel[Quelltext bearbeiten]

Laut Algorithmus müsste in dem Beispiel auf der Hauptdiagonalen jeweils unendlich statt Null stehen. Ist das ein Fehler im Algorithmus oder im Beispiel?--Doktor Wu (Diskussion) 09:42, 5. Jun. 2020 (CEST)[Beantworten]

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Diskussion:Algorithmus_von_Floyd_und_Warshall&oldid=200646438“