Szerkesztő:Gabesz79PFZ/Legrövidebb Út Gyorsabban algoritmus

A Legrövidebb Út Gyorsabban algoritmus (SPFA) a Bellman – Ford algoritmus továbbfejlesztése, amely kiszámítja az egy forrásból származó legrövidebb útvonalakat egy súlyozott irányított gráfban. Az algoritmus jól működik a véletlenszerű ritka gráfokon, és különösen alkalmas a negatív súlyú éleket tartalmazó gráfok útvonalainak kiszámításában. Az SPFA futási ideje legrosszabb esetben ugyanolyan, mint a Bellman–Ford-é, így a nemnegatív élsúlyú gráfok esetében a Dijkstra algoritmusát használják inkább. Az SPFA algoritmust Edward F. Moore publikálta először 1959-ben, a szélességi bejárás algoritmusának általánosításaképp. Az algoritmust később 1994-ben Fanding Duan fedezte fel újra önállóan.

Algoritmus

Egy adott súlyozott, irányított gráf $G=(V,E)$ és egy s forráscsúcs esetén az SPFA algoritmus megtalálja az $s$-ből az összes $v$ csúcshoz vezető legrövidebb utat. A legrövidebb út hossza $s$-ből $v$-be $d(v)$-ben van tárolva.

Az SPFA alapelve megegyezik a Bellman–Ford algoritmussal abban, hogy minden csúcsot megpróbál a szomszédaival összekötni. Ám az utóbbival ellentétben, itt nem véletlenszerűen próbáljuk végig az összes csúcsot, hanem az algoritmus egy, a megjelölt csúcsokat tartalmazó sort tart számon, amelyhez csupán akkor adunk új csúcsot, ha az már össze van kötve. A folyamat addig ismétlődik, amíg nem marad olyan csúcs, amit még össze lehetne kötni.

Az alábbiakban az algoritmus pszeudokódja látható. Itt $Q$ egy FIFO elvű sor (First In First Out; "Első be Első ki") mely a feldolgozandó csúcsokat tartalmazza. $w(u,v)$ pedig az $(u,v)$ csúcsok közötti élsúly értékét adja meg.

Egy példa az SPFA-ra az euklideszi távolság alapján. A vörös vonal jelöli az eddig talált legrövidebb utat. A kék vonal jelzi a kapcsolódás helyét, ami u és a Q-ban található. Ez egy rövidebb utat biztosít a forrásból v-hez.

 eljárás Legrövidebb-Út-Gyorsabban-Algoritmus(G, s)
 1     minden v ∈ V(G) csúcsra, ahol v ≠ s tedd
 2         d(v) := ∞
 3     d(s) := 0
 4     beillesztés(Q, s)
 5     amíg Q nem üres csináld
 6         u := Q első eleme (amely ekkor törlődik Q-ból)
 7         minden (u,v) élre E(G)-ben tedd
 8             ha d(u) + w(u, v) < d(v) akkor
 9                 d(v) := d(u) + w(u, v)
 10                ha v nincs Q-ban akkor
 11                    beillesztés(Q, v)

Az algoritmust egy irányítatlan gráf esetében is alkalmazhatjuk úgy, hogy minden irányítatlan élt kicserélünk két irányított, de ellentétes élre.

A helyesség igazolása

Bebizonyítjuk, hogy az algoritmus soha nem téved a legrövidebb út kiszámításában.

Állítás (Tétel) : A sor kiürültségének ellenőrzésekor, minden csúcs, amely jelenleg képes kapcsolódni, benne van a sorban.

Bizonyítás : Be akarjuk bizonyítani, hogy ha $dist[w]>dist[u]+wt(u,w)$ bármelyik két $u$ és $w$ csúcsra igaz a sor kiürültségének ellenőrzésekor, akkor $u$ a sorban tagja. Ezt indukció segítségével bizonyítjuk, melyet a már korában előfordult elemek ciklusain végzünk el. Fontos megjegyezni, hogy az állítás mindenképpen érvényes a ciklus megkezdése előtt: Ha $u\not =v$, akkor az összekapcsolás nem lehetséges. $u=v$ esetén viszont igen és ez rögtön hozzá is adódik a sorhoz még a ciklus megkezdődése előtt. Most nézzük meg mi történik a cikluson belül. Levesszük az $u$ csúcsot a sor elejéről és megpróbáljuk minden szomszédjával összekötni, ha ez lehetséges. Így, a ciklus iterációja befejeződése után $u$ már nem képes további kapcsolódásokat létesíteni, emiatt a sorból se kerül többet vissza. Viszont az $x$ általi kapcsolódás képessé tehet más csúcsokat arra, hogy kapcsolódást válthassanak ki. Ha a jelenlegi iteráció előtt már létezik olyan $x$ elem, mely kielégíti a $dist[x]>dist[w]+wt(w,x)$ feltételt, akkor $w$ már a sorban van. Ha ez a feltétel az iteráció közben válik igazzá, akkor vagy $dist[x]$ megnövekedett, ami lehetetlen, vagy pedig $dist[w]$ csökkent, utalva arra, hogy $w$ kapcsolódott. Miután $w$ kapcsolódott mindenképp a sor részévé válik, ha már eddig nem lett volna ott.

Következmény : Az algoritmus akkor és csak akkor ér véget, amikor további kapcsolódás már nem lehetséges.

Bizonyítás: Ha további kapcsolódás már nem lehetséges, az algoritmus folytatja a csúcsok eltávolítását a sorból, de újakat már nem ad hozzá, mivel ez csak csak sikeres kapcsolódások esetén történhet. Emiatt a sor kiüresedik és az algoritmus véget ér. Ha viszont még vannak lehetséges kapcsolódások, akkor a sor nem üresedik ki és az algoritmus folytatódik.

Az algoritmus nem ér véget, ha negatív súlyú hurkok érhetők el a forrásból. Lásd itt annak igazolását, hogy mindig lehet új kapcsolódást létrehozni, ha létezik egy vagy több negatív súlyú hurok. Egy olyan gráfban, ahol nincs negatív súlyú hurok, valamint nincs több kapcsolódási lehetőség, a helyes legrövidebb utak már ki vannak számítva (bizonyíték). Emiatt negatív súlyú hurkokat nem tartalmazó gráfok esetében, az algoritmus mindig a legrövidebb utak helyes hosszaival tér vissza.

Futási idő

Legrosszabb esetben az algoritmus futási ideje $O(|V|\cdot |E|)$, akárcsak a Bellman-Ford-féle algoritmus esetén. A kutatások azt mutatják, hogy az átlagos futási idő $O(|E|)$ mely véletlenszerű gráfok esetében valóban érvényes, azonban össze lehet állítani olyan ritka gráfokat, ahol az SPFA $\Omega (|V|^{2})$ időt igényel, akárcsak a Bellman-Ford-féle algoritmus.

Optimalizációs technikák

Az algoritmus teljesítményét erősen befolyásolja annak a sorrendje, ahogy a jelölt csúcsok a többi csúccsal való kapcsolódnak. Például, ha $Q$ egy prioritási sor volna, akkor az algoritmus viselkedése a Dijkstra-féle algoritmusra emlékeztetne. Itt azonban nem prioritási sort használunk, ezért legtöbbször két technikát alkalmaznak a sor minőségének javítására, melyek javítanak az átlagos eset teljesítményen, de a legrosszabb eset teljesítményén nem. Mindkét módszer átrendezi a $Q$-ban található elemek sorrendjét, hogy a forráshoz közelebbi a csúcsok elsőként kerülhessenek feldolgozásra. Ezen technikák alkalmazásakor $Q$ a megszokott FIFO-elvű sor helyett inkább egy átlagos duplán-láncolt lista vagy esetleg egy kettős végű sor.

A Small Label First (SLF; "Kis Címke Először") technika: A 11. sorban ahelyett, hogy a $v$ csúcsot mindig a sor végére tesszük, inkább összehasonlítjuk $d(v)$-t $d{\big (}{\text{elsőelem}}(Q){\big )}$-mel, és abban az esetben, ha $d(v)$ kisebb, $v$-t a sor elejére tesszük. Ezen technika pszeudokódja (miután a 11. sorban behelyeztük $v$-t a sor végére):

 eljárás SLF(G, Q)
    ha d(utolsóelem(Q)) < d(elsőelem(Q)) akkor
        u := Q utolsó eleme (mely ekkor törlésre kerül Q-ból)
        beillesztés_elejére(Q, u)

Large Label Last (LLL; "Nagy Címke Először") technika: A 11. sor után újrarendezzük a sort oly módon, hogy első helyre kerüljön egy az átlagnál kisebb elem, míg az olyan elemek, amik átlagnál nagyobbak pedig a sor végére kerülnek. Ezen technika pszeudokódja:

eljárás LLL(G, Q)
    x : = d(v) átlaga, ahol v ∈ Q
    amíg d(elsőelem(Q)) > x
        u := Q első eleme (mely ekkor törlésre kerül Q-ból)
        beillesztés_végére(Q, u)

Irodalom

[[Kategória:Gráfalgoritmusok]]