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