Implementácia

Zamyslime sa, ako takéto riešenie naprogramovať. Pamätať si graf vieme pomocou poľa susedov -- pre každý vrchol si pamätáme zoznam jeho susedov a kvôli šetreniu pamäte (a tiež času) používame dynamické polia ako je napríklad vector. Následne si môžeme do našeho programu pridať dve ďalšie polia. Pole V[], v ktorom si budeme pamätať najkratšiu vzdialenosť z vrchola a pre spracované vrcholy a pole D[], v ktorom si budeme pamätať najkratšiu cestu z $a$ idúcu iba cez spracované vrcholy pre všetky nespracované vrcholy.

V každom kole našeho algoritmu potom preiterujeme poľom D[], nájdeme vrchol s najmenšou hodnotou, tento vrchol prehlásime za spracovaný a upravíme hodnoty v poliach V[] a D[].

// V tomto poli si pamätáme graf ako zoznam susedov.
// V pair je prvé číslo suseda a potom dĺžka hrany do tohto suseda.
vector<vector<pair<int,int>>> G;
vector<int> D,V;
int n,m;
#define INF 2000000000

void pomala_dijkstra() {
    D.resize(n, INF);
    V.resize(n, INF);
    int a = 0; // začiatočný vrchol
    D[a] = 0;
    // postupne pridávame spracované vrcholy
    for (int i = 0; i < n; i++) {
        // nájdeme vrchol s najmenšou vzdialenosťou
        int v = 0;
        for (int j = 1; j < n; j++) {
            if (D[j] < D[v]) v = j;
        }
        if (D[v] == INF) break; // toto nastane, ak je napríklad nesúvislý
        // vrchol v prehlásime za spracovaný a upravíme príslušné hodnoty
        V[v] = D[v];
        D[v] = INF;
        for (int j = 0; j < G[v].size(); j++) {
            int w = G[v][j].first, dlz = G[v][j].second; // sused vrchola v a jeho vzdialenosť
            if (V[w] != INF) continue; // tento vrchol je už spracovaný
            D[w] = min(D[w], V[v] + dlz);
        }
    }
    // po skončení tejto funkcie máme v poli V[] najkratšie vzdialenosti od vrchola a
}

Jediný problém, ktorý takáto implementácia má je časová zložitosť. Prejsť poľom D[] a nájsť najmenší prvok totiž zaberie čas $O(n)$. A túto operáciu musíme spraviť n krát -- vždy keď prehlásime ďalší vrchol za spracovaný. Výsledná časová zložitosť takejto implementácie je teda $O(n^2)$.

Späť Ďalej