Floydin algoritmi
Tehtävä ratkeaa tyylikkäästi seuraavalla ns. Floydin algoritmilla:
- talletetaan taulukon D tyhjiin paikkoihin jokin hyvin suuri luku dmax (”ääretön”, esim. kaikkien D:n epätyhjien alkioiden summa)
- suoritetaan seuraavat kolme sisäkkäistä silmukkaa:
toista k:n arvoilla 1..n:
toista i:n arvoilla 1..n:
toista j:n arvoilla 1..n:
jos D[i,k] + D[k,j] < D[i,j],
niin aseta D[i,j] ¬ D[i,k] + D[k,j]
Algoritmin idea (lyhyesti kuvattuna) on, että kullakin silmukkamuuttujan k arvolla määritetään lyhimmät sellaiset kaupunkiparien i, j väliset reitit, jotka kulkevat enintään kaupunkien 1..k kautta.
Algoritmin aikavaativuus on selvästi luokkaa O(n3): kolme sisäkkäistä silmukkaa, kukin silmukka-muuttujan arvoilla 1..n.