12. óra
(Erben Péter, 2007. 12. 10.)
Gráfalgoritmusok 2. - Dijkstra algoritmusa
Élsúlyozott gráfokban (nemnegatív súlyok esetén) Dijkstra algoritmusával
határozható meg két pont között a legrövidebb út.
Dijkstra algoritmusa
Egy G nemnegatív számokkal súlyozott gráfban meghatározzuk,
egy s csúcsból kiindulva a többi csúcshoz vezető legrövidebb utat, és ezen
legrövidebb utak hosszát.
Dijkstra(G)
minden v csúcsra: d[v] := végtelen; apa[v] := null
d[s] := 0
Q := G
Ciklus amíg nemüres( Q )
u := kivesz_min(Q)
Ciklus u minden v szomszédjára
d2 = d[u] + hossz(u, v)
Ha d2 < d[v] akkor
d[v] := d2
apa[v] := u
Elágazás vége
Ciklus vége
Ciklus vége
Az
apa[] tömb a legrövidebb utakat adja meg, a csúcsoktól
s felé.
A
d[] tömbből olvashatók ki a távolságok.
Feladat
