iga i = 1, 2, …, n korral, iga j = 1, 2, …, n korral: kui aik + akj < aij, siis aij uus väärtus on aik + akj ja bij uus väärtus on bik. Asenduse idee: kui tipust i tippu k ja sealt tippu j liikudes on tee lühem, kui seni leitud lühim tee tipust i tippu j , siis liigume läbi tipu k . Näide 44 54. ** Floyd-Warshalli algoritmi keerukuse hinnang ja korrektsuse tõestus. [2] Floys-Warshalli algoritmi keerukuse hinnang o Miks leiab Floyd-Warshalli algoritm tõesti lühima võimaliku ahela iga kahe tipu vahel? o Kui lühima ahela i … j suurima indeksiga sisetipp on k, siis on algoritmi varasematel sammudel juba leitud lühimad ahelad i … k ja k … j ning otsitav lühim ahel leitakse seega üles k-ndal sammul. Tõestus o Korrektsuse teoreemi võib sõnastada nii:
annaabi.ee 
