Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2011-2012‎ > ‎

7. óra

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