10.7. Legrövidebb utak problémája

Adott egy G = (V,E) gráf és egy súlyfüggvény, amely az élekhez egy nemnegatív valós számot rendel. Egy út költsége az utat alkotó élekhez tartozó számok összege. A legrövidebb út súlya a minimális költségű út költsége. A feladatok természetét ől függően más és más értékek iránt érdeklődünk. A jellemző problémák a következők:

– Adott csúcsból induló legrövidebb utak problémája.

– Adott csúcsba érkező legrövidebb utak problémája.

– Adott csúcspár közötti legrövidebb út problémája.

– Összes csúcspár közti legrövidebb utak problémája.

10.7.1. Fokozatos közelítés

A gráf minden egyes pontjához hozzárendelünk egy valós számot, amely majd az adott csúcstól (s-től) való távolságát fogja tartalmazni. Ezt kezdetben az s kivételével végtelenre állítjuk. Továbbá felépítünk egy fát, mely az apák fele mutató mutatókból áll össze, s melynek a gyökere s. A kezdőértékek beállítását a KEZDŐ ÉRTÉK rutin végzi.

Procedure KEZDőÉRTÉK(G,s) 
Input: G gráf, s kezdőcsúcs 
Eredmény: a gráf csúcsaihoz végtelen távolságot rendel 
1 forall the v ∊ V do 
2    v.táv = ∾ 
3    v.apa = Nil 
4 endfall 
5 s.táv = 0 

A legrövidebb utakat meghatározó módszerek lényege a következő: sorra vesszük az éleket, s ha az adott élt használva rövidebb utat találunk, akkor frissítjük a megfelelő adatokat. Ehhez a frissítéshez a KÖZELÍT rutin tartozik.

Procedure KÖZELÍT(u,v,súly) 
Input: u, v csúcsok, súly élek súlyozása 
Eredmény: a v távolságát frissíti az u távolsága alapján 
1 if v.táv ≥ u.táv + súly(u, v) then 
2    v.táv = u.táv + súly(u, v) 
3    v.apa = u 
4 endif 

10.7.2. Dijkstra algoritmusa

Dijkstra algoritmusa egy S halmazt alkalmaz, mely azokat a csúcsokat tartalmazza, melyeknek már ismerjük a pontos távolságát. A Q tartalmazza a maradék csúcsokat. Ezeket a csúcsokat olyan adatszerkezetben tároljuk, melyet a csúcsok táv értékei alapján rendeztünk. Az algoritmus sorra megkeresi az S halmazhoz legközelebbi csúcsot, ezzel a csúccsal bővíti az S halmazt, majd ezen csúcs szomszédjainak kiszámítja a távolságát. Ha Q tárolására tömböt használunk, a bonyolultság O(V 2). Ritka gráfnál érdemes ugyanerre kupacot használni, s ekkor a bonyolultság O((V + E) ln(V ))

Procedure DIJKSTRA(G,s) 
Input: G gráf, s kezdőcsúcs 
Eredmény: a gráf csúcsainak az adott csúcstól mért távolságának meghatározása 
1  KEZDŐÉRTÉK(G,s) 
2  S = ∅ 
3  Q = V 
4  while Q != ∅ do 
5     u = KIVESZ-MIN(Q) 
6     S = S ⋃ {u} 
7     forall the v ∊ Adj(u) do 
8        KÖZELÍT(u,v,súly) 
9     endfall 
10 endw

10.7.3. Bellmann-Ford algoritmusa

A Bellmann-Ford algoritmus azokban az esetekben is működik, ha egyes élekhez negatív súlyok is tartoznak. Természetesen ha negatív súlyú kör szerepel a gráfban, akkor a minimális távolság nem definiálható. A külső ciklus annyiszor fut le, amilyen hosszú lehet a leghosszabb út. Minden egyes ciklusmagban eggyel messzebb található csúcsok távolságát határozzuk meg. Végül teszteljük, hogy van-e negatív súlyú kör. A két ciklusnak megfelelően a bonyolultság O(E ˇ V ).

Function BELLMANN-FORD(G,súly,s) 
Input: G gráf, súly élek súlyozása, s kezdőcsúcs 
Output: IGAZ, ha meghatározhatóak a minimális távolságok, s HAMIS, ha nem 
Eredmény: a gráf csúcsainak az adott csúcstól mért távolságának meghatározása 
1  KEZDŐÉRTÉK (G,s) 
2  for i = 1 to |V|-1 do 
3     forall the (u, v) ∊ E do 
4        KÖZELÍT(u,v,súly) 
5     endfall
5  endfor 
6  forall the (u, v) ∊ E do 
7     if v.táv ≥ u.táv + súly(u, v) then 
8        return HAMIS 
9     endif    
10 endfall 
11 return IGAZ

10.7.4. Irányított körmentes gráfok esete

Irányított körmentes gráfot O(V+E) bonyolultsággal topológikusan rendezhetjük a korábban már ismertetett módszerrel. Ezek után a legrövidebb utak meghatározásához csupán e rendezés alapján kell sorbalépkedni csúcsokon, s meghatározni a szomszédjaik távolságát.

Procedure IKG-LEGRÖVIDEBB-ÚT(G,súly,s) 
Input: G gráf, súly élek súlyozása, s kezdőcsúcs 
Eredmény: a gráf csúcsainak az adott csúcstól mért távolságának meghatározása 
1 KEZDŐÉRTÉK(G,s) 
2 forall the u ∊ V a topológikus rendezésnek megfelelően do 
3    forall the v 2 Adj(u) do 
4        KÖZELÍT(u,v,súly)
5    endfall 
6 endfall 

10.7.5. Legrövidebb utak meghatározása minden csúcspárra

A soron következő négy algoritmus bemenő adata egy W n × n-es mátrix. Ezen mátrix főátlójában 0 értékek szerepelnek, (minden csúcs távolsága saját magától zéró) míg ha a jelzett két pont között él található, akkor a mátrix adott pozíciójában az él súlya szerepel, egyébként végtelen. Az algoritmusok kimenete egy ugyancsak n×n-es mátrix, mely a megfelelő csúcsok közötti távolságot tartalmazza. Az ÚTBőVÍTÉS rutin minden egyes végrehajtásakor az eddig már kiszámolt utakat egy éllel bővít. (Az ÚTBőVÍTÉS rutinban a végtelenhez tetszőleges értékeket hozzáadva, nem végtelen értéket kivonva továbbra is végtelent kapunk eredményül.) Ha egy, a főátlójában 0, egyébként végtelen értékeket tartalmazó mátrixból indulnánk ki, akkor ez a nulla hosszúságú utakat tartalmazná. Az ÚTBőVÍTÉS rutint kell végrehajtani erre a mátrixra n−1-szer, miután a gráfban legfeljebb n−1 hosszú út található. Ezzel az algoritmus bonyolultsága O(V 4). Ha a kiinduló mátrix a W, akkor a bővítést csak n−2-szer kell végrehajtani (LASSÚ-LEGRÖVIDEBB-ÚT). Az útbővítés során egyszer már kiszámolt útsorozatokat is fel lehet használni, s aD mátrixot nem a W alapján frissítjük, hanem saját magát használva (GYORSABBLEGRÖVIDEBB- ÚT). Ezzel a bonyolultság O(V 3 ln V )-re csökken (A útbővítés rutinja nagyon hasonlít a mátrixszorzásra. Míg az első esetben „sorozatos szorzás” szerepel, a második esetben „sorozatos négyzetreemelés”.)

Function ÚTBőVÍTÉS(D,W) 
Input: D számolt távolságmátrix, W távolságmátrix az élek alapján 
Output: D’ továbbszámolt távolságmátrix 
1 n = sorok száma a W mátrixban 
2 D' = (d"ij) // n × n-es mátrix 
3 for i = 1 to n do 
4    for j = 1 to n do 
5       d'ij = ∾ 
6       for k = 1 to n do 
7          d'ij = min(d'ij , dik + wkj) 
8       endfor 
9    endfor 
10 endfor 
11 return D'

Function LASSÚ-LEGRÖVIDEBB-ÚT(W) 
Input: W távolságmátrix az élek alapján 
Output: D a gráf csúcsainak egymástól mért távolságaiból álló mátrix 
1 n = sorok száma a W mátrixban 
2 D = W 
3 for m = 2 to n − 1 do 
4    D = ÚTBŐVÍTÉS(D,W)
5 endf 
6 return D 

Function GYORSABB-LEGRÖVIDEBB-ÚT(W) 
Input: W távolságmátrix az élek alapján 
Output: D a gráf csúcsainak egymástól mért távolságaiból álló mátrix 
1 n = sorok száma a W mátrixban 
2 D = W 
3 m = 1 
4 while n − 1 ≥ m do 
5    D = ÚTBŐVÍTÉS(D,D) 
6    m = 2m 
7 endw 
8 return D 

10.7.6. Floyd-Warshall algortimus

Egy másik megközelítésben a gráf csúcsait csak korlátozottan vesszük igénybe, a k növekedésével egyre több és több csúcsot használhatunk az utak felépítésére. A három egymásba ágyazott ciklusnak megfelelően O(V 3) az algoritmus bonyolultsága.

Function FLOYD-WARSHALL(W) 
Input: W távolságmátrix az élek alapján 
Output: D a gráf csúcsainak egymástól mért távolságaiból álló mátrix 
1  n = sorok száma a W mátrixban 
2  D = W 
3  for k = 1 to n do 
4     for i = 1 to n do 
5        for j = 1 to n do 
6           dij = min(dij , dik + dkj) 
7        endfor 
8     endfor 
9  endfor 
10 return D