Dijkstrův algoritmus

Z CHWiki

Dijkstrov algoritmus je jedným z tých algoritmov, ktoré sa používajú na nájdenie najkratšej cesty v grafe. Jeho pochopenie a implementácia je otázkou krátkeho času aj pre programátorov začiatočníkov. Výpočtová zložitosť algoritmu je O(n²).

---

Princíp

Dijkstrov algoritmus je jeden z najpoužívanejších pre nájdenie najkratšej cesty v grafe. Je to jednoduchý nerekurzívny (je ho samozrejme možné napísať aj rekurzívne, ale rekurzívna implementácia je úplne neprirodzenejá) algoritmus, ktorého princíp je zjavný z nasledujúcich obrázkov.

Chceme sa dostať z červeného vrchola do modrého, červený vrchol pridáme do fronty.

Ak nie je fronta prázdna, vyberieme prvý vrchol, a do fronty pridáme všetkých jeho susedov, ktorých sme ešte nenavštívili. Pre každý vrchol si zapamätáme, ako sme sa tam dostali.

Opakujeme predchádzajúci krok, pokiaľ sme sa nedostali do cieľa alebo vo fronte už nie je žiaden vrchol - cesta neexistuje.

[editovat] Implementácia

Graf budeme reprezentovať dvojrozmerným poľom. Algoritmus predpokladá, že všetky vrcholy spojené hranou majú rovnakú vzdialenosť. Ak by boli hrany ohodnotené, museli by sa vrcholy vo fronte usporiadať podľa prejdenej vzdialenosti. Ak graf[i][j] = 1, potom z vrchola i do vrchola j vedie hrana

Musíme si pamätať, či sme daný vrchol navštívili a ako sme sa tam dostali. Toto sa dá spraviť jedným poľom, my pre jednoduchosť použijeme dve, from a visited.

function cesta(source, dest)
    fronta Q
    Q = Q U {source}
    visited[source] = true
    while(not (Q = {})) do
        v = vyber prvý prvok z fronty Q
        // vrchol sa rovná koncu, našli sme cestu
        if(v = dest)
            cesta := true
        endif
        // prejdeme všetky vrcholy
        for i := 1 to VERT_NUM do
             // ak sú vrcholy v a i susedné, a vrchol i nebol ešte navštívený
             if graf[i][v] = 1 and visited[i] = false
              	 // pridáme ho do fronty
                Q = Q U {i}
                // zapamätáme si, že do vrchola i sme sa dostali z vrchola v
                from[i] = v
                // zapamätáme si, že vrchol i sme už navštívili
                visited[i] = true
            end if
        end for
    end while
    // fronta ostala prázdna, cesta neexistuje
    cesta := false
end function

Po vykonaní funkcie cesta obsahuje prvok poľa from[i] údaje o tom, z ktorého vrchola sa algoritmus dostal do vrchola i, z čoho sa dá spätne vypísať celá cesta.