Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2014-2015‎ > ‎

16. alkalom

Legrövidebb út algoritmusokat nézünk át. Az algoritmusok több szempontból osztályozhatók:
  • Egyetlen csúcsból induló legrövidebb utak keresése / összes csúcspár közötti legrövidebb út keresése
  • Gráffal megadott "térkép" / táblázattal megadott "térkép"
  • Súlyozott élek / súlyozatlan élek
  • Csak nemnegatív élsúlyok lehetnek / lehetnek negatív súlyok, de nem lehet negatív összsúlyú kör / lehet negatív kör 
Különbség az is, hogy csak a pontpárok távolságát szeretnénk kiszámolni, vagy elő is kell állítanunk a legrövidebb utakat.

Elmélet

A következőkben többször használni fogunk egy d[i][j] értéket, ami az i és j csúcs közötti legrövidebb út pillanatnyi becslése. Ha egyetlen csúcsból induló utakat számolunk, akkor elég egy index: d[j] a j csúcsba vezető (pillanatnyilag) legrövidebb út hossza.
Az i--j él súlya w[i][j] lesz. Közelítésnek vagy relaxálásnak a következő lépést nevezzük:

Közelít(start,u,v):
    Ha d[start][u] + w[u][v] < d[start][v] akkor
        d[start][v] := d[start][u] + w[u][v]
        apa[v] := u
    Elágazás vége
Eljárás vége

Az apa[v] érték azt mutatja meg, hogy honnan léptünk v-be, amikor a d[start][v] értéket meghatároztuk. 

A folytatásban használjuk az élek száma = E és csúcsok száma = V jelöléseket.

Bellman-Ford algoritmus

Egy csúcsból kiinduló legrövidebb utakat számolja ki súlyozott gráfban, megengedi a negatív élsúlyokat, és fel tudja fedezni a negatív köröket.

minden v csúcsra:
    Ha v = start akkor 
        d[start][v] := 0
    különben
        d[start][v] := végtelen
    Elágazás vége
    apa[v] := nem definiált

Ciklus (V-1)-szer
    Ciklus minden (u,v) élre
        közelít(start, u , v)
    Ciklus vége
Ciklus vége

Helyesség: A ciklus i. lefutása után d[start][i] a legrövidebb út hossza, amely legfeljebb i élből áll.
Negatív körök felderítése: a főátlóban megjelenő negatív szám.

Floyd-Warshall algoritmus

Az összes csúcspár közötti legrövidebb utat számolja ki (az út hosszát), megengedi a negatív élsúlyokat.

minden v csúcsra:
    d[v][v] := 0

minden (u,v) élre:
    d[u][v] := w[u][v]

Ciklus k := 1-től V-ig
    Ciklus i := 1-től V-ig
        Ciklus j := 1-től V-ig
            Ha d[i][j] > d[i][k] + d[k][j] akkor
                d[i][j] := d[i][k] + d[k][j]
            Elágazás vége
        Ciklus vége
    Ciklus vége
Ciklus vége

Ha nincs u -> v él, akkor w[u][v] "végtelen".
Helyesség: A külső ciklus k. lefutása után d[i][j] a legrövidebb út hossza, amelyben i és j között, csak az 1,2,...,k csúcsokat használhatjuk.
Negatív körök felfedezése: +1-szer lefuttatjuk a főciklust, és megnézzük, hogy csökken-e valamelyik d[i][j]. 

Dijkstra-algoritmus

Egy csúcsból kiinduló legrövidebb utakat számolja ki irányított, nemnegatív súlyokkal súlyozott gráfon.

minden v csúcsra:
    d[start][v] := végtelen
    apa[v] := nemdefiniált

d[start][start] = 0
prioritási-sorba (összes csúcs)
Ciklus amíg nem üres a prioritási sor
    u := kivesz-min-a-prioritási-sorból()
    Ciklus az (u,v) éleken
        Közelít(start, u, v) // módosul a prioritási sor rendezése!
    Ciklus vége
Ciklus vége

Szélességi bejárás

Egy csúcsból kiinduló legrövidebb utak súlyozatlan gráf esetén. Ilyenkor az út hossza a benne szereplő élek száma.

minden v csúcsra:
    d[start][v] := végtelen
    apa[v] := nemdefiniált

d[start][start] := 0
Sorba(start)
Ciklus amíg nem üres sor
    u := Sorból()
    Kész[u] := igaz
    Ciklus az (u,v) éleken
        Ha nem Kész[v] akkor
            d[start][v] := d[start][u] + 1
            apa[v] := u
            Sorba(v)
        Elágazás vége
    Ciklus vége
Ciklus vége



Feladatok