Floyd Warshall algoritmus

Nem tudod kiválasztani a legrövidebb utat a helyedtől a célállomásig?. Akkor ismernie kell ezt az algoritmust.

• Aloyd-Warshall algoritmust arra használják, hogy megtalálják a legrövidebb utakat egy gráf minden csúcspárja között, ahol a gráf minden egyes élének van egy súlya, amely pozitív vagy negatív.
• Az algoritmus használatának legnagyobb előnye, hogy bármely 2 csúcs közötti legrövidebb utakat O(V3) alatt lehet kiszámítani, ahol V a gráf csúcsainak száma.
• A Floyd-Warshall algoritmust Floyd algoritmusnak, Roy-Floyd algoritmusnak, Roy-Warshall algoritmusnak vagy WFI algoritmusnak is nevezik.
• Az algoritmus a dinamikus programozási megközelítést követi a legrövidebb utak megtalálásához.

Algoritmus

N csúcsú gráf esetén:

1. lépés: Kezdjük el a legrövidebb utakat bármely 2 csúcs között Infinity-vel.

2. lépés: Keressük meg az összes olyan pár legrövidebb utat, amely 0 közbenső csúcsot használ, majd keressük meg az 1 közbenső csúcsot használó legrövidebb utakat és így tovább… amíg az összes N csúcsot használjuk közbenső csomópontként.

3. lépés: Minimalizáljuk a legrövidebb utakat bármely 2 pár között az előző műveletben.

4. lépés: Bármely 2 csúcs (i,j) esetén valójában a pár közötti távolságokat kell minimalizálni az első K csomópontot használva, így a legrövidebb út a következő lesz: min(dist+dist,dist).

a dist a legrövidebb utat jelenti, amely csak az első K csúcsot használja, dist a legrövidebb utat jelenti a k,j pár között. Mivel a legrövidebb út az i-től k-ig, majd a k-tól j-ig tartó legrövidebb út összevonása lesz.

for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist = min( dist, dist + dist );
}
}
}

Példa

Legyen az adott gráf:

Az összes csúcspár közötti legrövidebb út megkereséséhez kövessük az alábbi lépéseket.

1. Készítsünk egy A0 dimenziós n*n mátrixot, ahol n a csúcsok száma. A sort és az oszlopot i-vel, illetve j-vel indexeljük. i és j a gráf csúcsai.

Minden A cellába az ith csúcs és a jth csúcs közötti távolságot írjuk be. Ha nincs út a ith csúcsból a jth csúcsba, akkor a cella végtelen marad.

2. Most hozzunk létre egy A1 mátrixot a A0 mátrix segítségével. Az első oszlop és az első sor elemeit hagyjuk úgy, ahogy vannak. A többi cellát a következő módon töltjük ki:

Legyen k a forrástól a célállomásig tartó legrövidebb út fagypontja. Ebben a lépésben k az első csúcs. A a (A + A) if (A > A + A).

Ha a forrástól a célállomásig a közvetlen távolság nagyobb, mint a k csúcson átvezető út, akkor a cellát a A + A.

Ebben a lépésben k az 1. csúcs. Kiszámítjuk a távolságot a forráscsúcstól a célcsúcsig ezen a k csúcson keresztül.

Például: A A1 esetében a 2. csúcs és a 4. csúcs közötti közvetlen távolság 4, és a 2. csúcs és a 4. csúcs közötti távolságok összege a csúcson keresztül (azaz a 2. csúcsról az 1. csúcsra és az 1. csúcsról a 4. csúcsra) 7. Mivel 4 < 7, a A0 fel van töltve 4.

3. Hasonló módon a A2 a A3 segítségével jön létre. A második oszlop és a második sor elemeit változatlanul hagyjuk.

Ebben a lépésben k a második csúcs (azaz a 2. csúcs). A további lépések ugyanazok, mint a 2. lépésben.

4. Hasonlóképpen létrejön a A3 és a A4 is.

A4 adja az egyes csúcspárok közötti legrövidebb utat.

A legrövidebb út kiválasztásához használjuk az alábbi kódot. De adja meg a helyes távolságokat.

Az időbonyolultság

Három hurok van. Mindegyik huroknak állandó bonyolultsága van. Tehát a Floyd-Warshall-algoritmus időbonyolultsága O(n3).

Térbonyolultság

A Floyd-Warshall-algoritmus térbonyolultsága O(n2).

A Floyd-Warshall-algoritmus térbonyolultsága O(n2).