next up previous contents
Nächste Seite: Transitive Hülle Aufwärts: Das Kürzeste-Wege-Problem Vorherige Seite: Algorithmus von Bellmann-Ford   Inhalt

Algorithmus von Floyd

Bemerkung:
Seien nun alle Knoten eindeutig von 1 aufsteigend durchnummeriert (Indizes).

Algorithmus:
Der Algorithmus von Floyd löst das APSP-Problem mit Dynamischer Programmierung. Sei $ c_{ij}^k$ Länge des Pfades von $ v_i$ nach $ v_j$ über die ersten $ k$ Knoten. Gesucht ist $ c_{ij}^n$.
Es gilt: $ c_{ij}^k = min \{ c_{ij}^{k-1}, c_{ik}^{k-1} + c_{kj}^{k-1} \} $

Pseudocode:
for $ k$ = 1 to $ n$
for $ i$ = 1 to $ n$
for $ j$ = 1 to $ n$
$ c[i][j] = min \{ c[i][j], c[i][k] + c[k][j] \} $

Komplexität:
Der Algorithmus von Floyd löst das APSP-Problem in Zeit $ O(n^3)$. Für große $ n$ ist der Algorithmus von Dijkstra (angewandt auf alle Knoten) schneller.



2003-10-08