2011.11.07.
A legrövidebb utak témakörének következő állomása: útkeresés irányított élsúlyozott gráfban. Feltesszük, hogy nincsenek negatív élek, ami reális feltevés, ha az élsúlyok valódi utak hosszát vagy a megtételükhöz szükséges időt jelképezik.
Feladat
Dijkstra algoritmusa
Dijkstra(G, s):
// inicializálás
Ciklus a G gráf minden v csúcsára
d[v] := végtelen
apa [v] := nemdefiniált
Ciklus vége
d[s] := 0
Sorba(s)
apa[s] := s
// számolás
Ciklus amíg nem üres a Sor
u := kivesz_minimum( Sor )
Ciklus az u összes v szomszédjára
Ha d[v] = végtelen akkor
d[v] := d[u] + w(u,v)
apa[v] := u
Sorba( v )
különben
tav := d[u] + w(u, v)
Ha tav < d[v] akkor
d[v] := tav
apa [v] := u
Elágazás vége
Elágazás vége
Ciklus vége
Ciklus vége
Eljárás vége
Ugyanez picit tömörebben, ha a "végtelen"-t olyan értékkel kódoltuk, ami szerepelhet összehasonlításban:
Dijkstra(G, s):
// inicializálás
Ciklus a G gráf minden v csúcsára
d[v] := végtelen
apa [v] := nemdefiniált
Ciklus vége
d[s] := 0
apa[s] := s
Sorba( G összes csúcsa )
// számolás
Ciklus amíg nem üres a Sor
u := kivesz_minimum( Sor )
Ciklus az u összes v szomszédjára
tav := d[u] + w(u, v)
Ha tav < d[v] akkor
d[v] := tav
apa [v] := u
Elágazás vége
Ciklus vége
Ciklus vége
Eljárás vége
Példa
|