Informatik Algorithmen – Floyd-Warshall
Karteikarten zum Thema „Informatik“ · 14 Karten · von atrio. Beispiele: Welches Problem löst der Floyd-Warshall-Algorithmus? · Wie lautet die asymptotische L…
Karten
14 KartenWelches Problem löst der Floyd-Warshall-Algorithmus?
Rückseite
Er berechnet kürzeste Pfade zwischen allen Knotenpaaren in einem gewichteten Graphen (All-Pairs Shortest Paths).
Wie lautet die asymptotische Laufzeitkomplexität von Floyd-Warshall?
Rückseite
O(V³) durch drei verschachtelte Schleifen über alle Knoten; V ist die Knotenzahl.
Wie hoch ist die Speicherkomplexität bei Adjazenzmatrix-Darstellung?
Rückseite
O(V²) für die Distanzmatrix und optional die Vorgänger-Matrix zur Pfadrekonstruktion.
Welche Kanten-Gewichte verträgt Floyd-Warshall?
Rückseite
Positive und negative Gewichte sind erlaubt; negative Zyklen dürfen nicht existieren.
Wie erkennt der Algorithmus negative Zyklen?
Rückseite
Nach Abschluss prüft man die Diagonale der Distanzmatrix: ein negativer Wert d[i][i] < 0 signalisiert einen negativen Zyklus.
Was besagt die Rekursionsformel dᵏ[i][j] = min(dᵏ⁻¹[i][j], dᵏ⁻¹[i][k] + dᵏ⁻¹[k][j])?
Rückseite
Der kürzeste Pfad von i nach j nutzt entweder nur Knoten < k als Zwischenknoten oder geht über Knoten k.
Welche Datenstruktur bildet die Basis der Implementierung?
Rückseite
Eine V×V-Adjazenzmatrix für Kanten-Gewichte, initialisiert mit ∞ für fehlende Kanten und 0 auf der Diagonale.
Wie wird die initialisiere Distanzmatrix D⁰ gefüllt?
Rückseite
D⁰[i][j] = Kantengewicht bei Kante (i,j), 0 für i=j, sonst ∞ (unendlich).
Wozu dient die Vorgänger-Matrix (Next-Matrix) bei Floyd-Warshall?
Rückseite
Sie speichert den nächsten Knoten auf dem kürzesten Pfad und ermöglicht die vollständige Pfadrekonstruktion in O(Pfadlänge).
Warum ist Floyd-Warshall für dünne Graphen oft schlechter als wiederholtes Dijkstra?
Rückseite
Floyd-Warshall braucht immer O(V³), während Dijkstra mit Fibonacci-Heap O(V·E + V² log V) schneller ist bei E ≪ V².
Kann Floyd-Warshall für transitive Hülle eines Graphen genutzt werden?
Rückseite
Ja: Ersetze Min durch logisches OR und Addition durch AND; Ergebnis zeigt Erreichbarkeit zwischen allen Knotenpaaren.
Was ist der Unterschied zwischen Floyd-Warshall und Bellman-Ford?
Rückseite
Bellman-Ford löst Single-Source Shortest Paths in O(V·E), Floyd-Warshall All-Pairs in O(V³); beide erlauben negative Gewichte.
Wie lautet die korrekte Schleifenreihenfolge in der Standard-Implementierung?
Rückseite
Äußere Schleife über k (Zwischenknoten), innere über i (Start) und j (Ziel); Reihenfolge von i/j ist vertauschbar.
Wann ist Floyd-Warshall gegenüber Johnson-Algorithmus vorzuziehen?
Rückseite
Bei dichten Graphen (E ≈ V²) und wenn Implementierungseinfachheit wichtiger ist als asymptotische Optimalität für dünne Graphen.