Modifikation von Floyd's-Algorithmus

Falls kein negativer Kreis existiert, funktioniert der Algorithmus weiterhin korrekt.

$\parbox{5cm}{ $c_{16}^6 = 5 = c_{16}^5$\space \\ \\ $c_{61}^6 = -6 = c_{61}^5$\space \\ \\ $c_{11}^6 = \min \{c_{11}^5,c_{16}^5+c_{61}^5 \} =-1 $ }$

$\Rightarrow$ der Graph enthält einen negativen Kreis, g.d.w. ein c_iiⁿ < 0 existiert.

Man kann also in den Algorithmus von Floyd einen Test auf negative Kreise einbauen, indem man direkt vor der Ausgabe den folgenden Befehl einfügt:

for i 1 to n do
		 if ciin < 0 then stop.