Floyd-Warshallův algoritmus pracuje na orientovaném grafu, který neobsahuje záporné cykly1 (to nám nezápornost hran bez problémů zaručí), a najde nejkratší orientované cesty mezi každou dvojicí vrcholů. Navíc ze všech cest stejné délky vybere tu s nejmenším počtem hran.

Pokud chceme spočítat vzdálenost každé dvojice vrcholů, tak můžeme $n$-krát použít Dijkstrův algoritmus (na každý vrchol). Lepší možností je použít Floyd-Warshallův algoritmus, který počítá všechny vzdálenosti přímo, proběhne rychleji než $n$-krát použitý Dijkstrův algoritmus a ještě se snadněji implementuje. Dokonce je tak jednoduchý, že pokud nám nebude záležet na časové složitosti, ale jen na rychlosti naprogramování, tak je lepší volbou než Dijkstrův algoritmus.

Vrcholy grafu očíslujeme čísly od jedničky do $n$. Vzdálenosti mezi každou dvojicí vrcholů si budeme ukládat do matice $n\times n$. Celý trik Floyd-Warshallova algoritmu spočívá v tom, že vzdálenosti nepočítáme přímo, ale v $n$ iteracích.

V $i$-té iteraci spočítáme matici $D^i$. Hodnota $D^i[u,v]$ je délka nejkratší cesty z $u$ do $v$, která smí procházet pouze přes vrcholy $\{1,2,\dots,i\}$. Jinými slovy $D^i[u,v]$ je délka nejkratší cesty v podgrafu indukovaném vrcholy $\{1,2,\dots,i\}$.2 V nulté iteraci začneme s maticí $D^0$. Hodnota $D^0[u,v]$ je délka hrany $uv$, pokud z $u$ vede hrana do $v$, nula na diagonále a nekonečno jinak. Matice $D^0$ je tedy matice vzdáleností (upravená matice sousednosti, která místo jedniček obsahuje délky hran a místo nul mimo diagonálu nekonečna). V poslední iteraci skončíme s maticí $D^n$, která už bude obsahovat hledané vzdálenosti, protože cesty mezi $u$ a $v$ smí procházet přes všechny vrcholy.

Pozorování: $D^{i}[u,v] = \min\{\,D^{i-1}[u,v]\,,\, D^{i-1}[u,i] + D^{i-1}[i,v] \,\}$

Nejkratší cesta mezi $u$ a $v$, která smí procházet pouze přes vrcholy $\{1,2,\dots,i\}$, buď projde přes vrchol $i$ a nebo ne. Pokud nejkratší cesta neobsahuje $i$, tak je její délka $D^{i-1}[u,v]$. V opačném případě cestu rozložíme na dva úseky—před příchodem do $i$ a po jeho opuštění. Ani jeden z úseků neobsahuje $i$ a tak je délka této cesty $D^{i-1}[u,i] + D^{i-1}[i,v]$.

Mohli byste namítnout, že nemůžeme délky úseků jen tak sečíst, protože oba úseky mohou obsahovat stejný vrchol $w$. Složení úseků by nebyla cesta, ale jen tah. V tom případě můžeme část tahu mezi oběma výskyty $w$ vypustit (cyklus z $w$ do $i$ a zpět) a dostaneme kratší tah, který už je cestou. Délka tahu se zkrátila, protože graf neobsahuje záporné cykly. Nově vzniklá cesta už neobsahuje $i$ a byla uvažována v prvním případě.

Pozorování: Hodnoty $D^{i-1}[*,i]$ a $D^{i-1}[i,*]$ se v $i$-té iteraci nezmění. Nebo-li $D^i[*,i]=D^{i-1}[*,i]$ a $D^i[i,*]=D^{i-1}[i,*]$ (hvězdička značí libovolný index).

Pozorování plyne z předchozího pozorování a faktu, že $D^{j}[w,w]$ je rovno nule pro každé $j$ a $w$. K výpočtu $D^{i}[u,v]$ potřebujeme znát jen hodnoty $D^{i-1}[u,v]$, $D^{i-1}[u,i]$, $D^{i-1}[i,v]$, ale poslední dvě hodnoty se během $i$-té iterace nezmění. Proto můžeme nové hodnoty $D^{i}[u,v]$ zapisovat do stejné matice jako předchozí iteraci. Přepsanou položku $D^{i-1}[u,v]$ už nebude během iterace potřebovat. V celém algoritmu si tedy vystačíme jen s jednou maticí $D[*,*]$, do které budeme zapisovat všechny iterace. Floyd-Warshallův algoritmus vypadá následovně:

$D:=D^0$      { matice vzdáleností}
for $i=1$ to  $n$ do
    for $u=1$ to  $n$ do
    for $v=1$ to  $n$ do
         if $D[u,v]>D[u,i]+D[i,v]$ then
            $D[u,v]:=D[u,i]+D[i,v]$

Časová složitost Floyd-Warshallova algoritmu je $\OO(n^3)$.3 Pokud si chceme zapamatovat kudy nejkratší cesty vedou, tak si v průběhu algoritmu budeme pro každou dvojici $u$,$v$ pamatovat nejvyšší číslo vrcholu, přes který nejkratší cesta vede (poslední volbu $k$, která vedla ke zkrácení cesty). Z toho už se dá nejkratší cesta zrekonstruovat pomocí rekurze.