Floyd-Warshalluv algoritmus slouzi k nalezeni vsech nejkratsich cest v grafu, tedy nejkratsich cest pro vsechny dvojice vrcholu grafu. Algoritmus ma kubickou asymptotickou casovou slozitost vzhledem k poctu vrcholu. Stejne casove slozitosti dosahneme, mimochodem, i pouzitim Dijkstrova algoritmu aplikovaneho na kazdy vrchol grafu. Floyd-Warshalluv algoritmus je vsak ponekud jednodussi a primocarejsi. Operuje vsak s matici sousednosti, kterou je nutno, pouzivame-li obvyklou reprezentaci grafu dynamickymi strukturami, specialne vytvorit.

Floyd-Warshalluv algoritmus:

Vstup: ohodnoceny graf G reprezentovany incidencni matici W[u,v]

n:=pocet uzlu grafu G (rozmer matice W)
D:=W (zkopirovani obsahu matice W do matice D)
for k:=1 to n do
  for i:=1 to n do
    for j:=1 to n do
      D[i,j]:=min(D[i,j],D[i,k]+D[k,j])
    end for
  end for
end for

Vystup: matice D obsahuje pro vsechny dvojice uzlu
                 jejich minimalni vzdalenost (delku nejkratsi cesty)

Poznamka: pokud pustime Floyd-Warshalluv algoritmus na booleanovskou incidencni matici (napriklad mame-li neohodnoceny graf), prejde D[i,j]:=min(D[i,j],D[i,k]+D[k,j]) v   D[i,j]:=or(D[i,j],D[i,k] and D[k,j]). Vysledna booleanovska matice D pak bude matici souvislosti: tedy matici, kde D[i,j] rika, zda mezi vrcholy i a j existuje nejaka cesta ci nikoliv.