8. óra
Nekilátunk a gráfalgoritmusok átnézésének. Először távolságokat számolgatunk gráfokban.
Floyd-Warshall algoritmus
A probléma
Adott egy (esetleg élsúlyozott, irányított) gráf. Határozzuk meg az összes pontpárra a gráfban számított távolságokat. Két pont (i és j) távolsága a legrövidebb
i-ből j-be vezető út hossza. Az út hossza pedig a benne szereplő (irányított) élek összsúlya. Ha a gráf súlyozatlan, akkor az út hossza a benne szereplő élek száma, tehát úgy számolhatunk, mintha minden súly egységnyi lenne.
A megoldási ötlet
Az i-ből j-be vezető út hosszát több lépésben számoljuk ki.
Bevezetjük a $d_k(i,j)$ függvényt, ami az i-ből j-be vezető olyan utak közül a legrövidebb hossza, amelyek i-től és j-től eltekintve csak az 1,2,...,k csúcsokon haladnak át. (Nem feltétlenül mindegyiken.)
Ekkor $d_0(i,j)$ az (i,j) él hossza, ha i és j különbözik és van köztük él, végtelen, ha nincs köztük él, és $d_0(i,i)=0$.
Feladatunk $d_n(i,j)$ kiszámítása, ezt n lépésben tesszük meg, k=1,2,...,n-re meghatározzuk $d_k(i,j)$-t.
A számítása alapja a következő rekurzió:
$d_k(i,j)=\min(d_{k-1}(i,j), d_{k-1}(i,k)+d_{k-1}(k,j))$
Az algoritmus
kezdetben minden i,j-re legyen d[i,j] az (i,j) él hossza, d[i,i] pedig 0
amennyiben nincs (i,j) él, olyankor d[i,j]=végtelen
Ciklus k := 1-től n-ig
Ciklus i := 1-től n-ig
Ciklus j := 1-től n-ig
d[i,j] = min(d[i,j], d[i,k] + d[k,j])
Ciklus vége
Ciklus vége
Ciklus vége
Az algoritmusban nem használtuk a $k$ indexet. Gondoljuk végig, hogy ez nem befolyásolja az algoritmus helyességét.
Feladat
