12. óra
Címkék > Óra

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

Indiana Jones