Informatika gyűjtemény

Egy szinttel feljebb 12. óra

2004050607080910

NézetNyomtat

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