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 Länge des Pfades von nach über die ersten Knoten.
Gesucht ist .
Es gilt:
Pseudocode:
for = 1 to
for = 1 to
for = 1 to
Komplexität:
Der Algorithmus von Floyd löst das APSP-Problem in Zeit .
Für große ist der Algorithmus von Dijkstra (angewandt auf alle Knoten) schneller.