Dijkstrin algoritam — najkraći putevi u grafu

Dijkstrin algoritam pronalazi najkraće rastojanje od jednog početnog čvora do svih ostalih čvorova u grafu. Radi ispravno samo ako su sve težine grana nenegativne.

Ovo je jedan od najvažnijih algoritama u grafovima i spada u greedy algoritme. Na svakom koraku bira čvor sa najmanjom trenutno poznatom udaljenošću i "zapečati" njegov rezultat.

Kada koristiti Dijkstru?

Algoritam koristi se kada:

graf ima težine (dužine, vreme, cena...)
sve težine su nenegativne
želimo najkraći put od polaznog do svih ostalih čvorova

Primeri:

navigacija na mapi (Google Maps, GPS)
najbrži način da pređemo nivo u video igri
optimizacija mreža i protoka podataka
najkraća ruta kroz maze/lavirint

Ideja algoritma

Za svaki čvor čuvamo udaljenost od starta. Na početku, udaljenost startnog čvora je 0, a svih ostalih je beskonačno (∞).

Na svakom koraku:

izaberemo neobrađen čvor sa najmanjom udaljenošću (greedy korak)
pokušamo da relaksiramo (poboljšamo) susedne čvorove
ponavljamo dok ne obradimo sve čvorove

Relaksacija:


ako je dist[u] + w(u,v) < dist[v]:
    onda ažuriraj dist[v]

Implementacija (C++) — verzija sa `priority_queue`

Najbolja i najčešća implementacija koristi prioritetni red (min-heap).


#include 
using namespace std;

const int INF = 1e9;

vector> graf[100]; 
// graf[x] = lista parova (sused, težina)

vector d; // udaljenosti

void dijkstra(int start, int n){
    d.assign(n+1, INF);
    d[start] = 0;

    priority_queue, vector>, greater>> pq;
    pq.push({0, start}); // (udaljenost, čvor)

    while(!pq.empty()){
        auto [dist, v] = pq.top();
        pq.pop();

        if(dist > d[v]) continue; // preskačemo ako nije aktuelno

        for(auto [sused, w] : graf[v]){
            if(d[v] + w < d[sused]){
                d[sused] = d[v] + w;
                pq.push({d[sused], sused});
            }
        }
    }
}

Korišćenje:


int main(){
    int n = 5; // broj čvorova

    // dodavanje grana (u, v, tezina)
    graf[1].push_back({2, 7});
    graf[1].push_back({3, 9});
    graf[2].push_back({4, 10});
    graf[3].push_back({4, 2});
    graf[4].push_back({5, 1});

    dijkstra(1, n);

    for(int i=1; i<=n; i++)
        cout << "distanca do " << i << " = " << d[i] << endl;
}

Rekonstrukcija najkraćeg puta

Da bismo znali konkretan put, čuvamo prethodnika (parent) svakog čvora.


// dodati uz postojeći kod

vector parent;

void dijkstra(int start, int n){
    d.assign(n+1, INF);
    parent.assign(n+1, -1);
    d[start] = 0;

    priority_queue, vector>, greater>> pq;
    pq.push({0, start});

    while(!pq.empty()){
        auto [dist, v] = pq.top();
        pq.pop();

        if(dist > d[v]) continue;

        for(auto [sused, w] : graf[v]){
            if(d[v] + w < d[sused]){
                d[sused] = d[v] + w;
                parent[sused] = v;      // pamti putanju
                pq.push({d[sused], sused});
            }
        }
    }
}

// funkcija za vraćanje puta
vector rekonstruiši_put(int cilj){
    vector put;
    for(int v = cilj; v != -1; v = parent[v])
        put.push_back(v);
    reverse(put.begin(), put.end());
    return put;
}


// primer poziva
auto put = rekonstruiši_put(5);
for(int x : put) cout << x << " ";

Vizuelni primer

Graf:

1 →2 (7), 1→3 (9), 3→4 (2), 4→5 (1), 2→4 (10)

Izvor: 1

Najkraći put 1 → 3 → 4 → 5 = 12

Greške koje treba izbegavati

Ne sme biti **negativnih težina** (onda se koristi Bellman-Ford).
Ne sme se završiti kada se pusti cilj — Dijkstra ide dok se svi ne obrade.
Ne porediti nova rastojanja bez provere `if(dist > d[v]) continue;`.

Složenost algoritma

Struktura	Složenost
Prioritetni red (heap)	O((V + E) log V)
Matrična reprezentacija	O(V²)

Vežba

Za vežbu, probaj da:

Pronađeš najkraći put u mreži gradova (kao GPS)
Napraviš program koji vraća sve čvorove na rastojanju ≤ K
Implementiraš obrnuti algoritam: traženje najdaljeg čvora

Sledeća preporučena lekcija

□ Nastavljamo sa minimalnim razapinjućim stablima:

Bellman-Ford i Floyd-Warshall algoritmi

Vraćanje na vodič za oblast "Grafovi i stabla"

← Mapa učenja — Grafovi i stabla