BFS nalazi najkraći put kada sve grane imaju istu dužinu. Kada grane imaju različite dužine (kilometri, minuti, cene), koristi se Dijkstrin algoritam. Radi za grafove čije težine nisu negativne i uz priority_queue obrađuje i milion grana za delić sekunde.
4
1 ------- 2
| \ |
1 | \ 7 | 2
| \ |
3 ------- 4 ---- 5
5 3
Grane: 1–2 (4), 1–3 (1), 1–4 (7), 2–4 (2), 3–4 (5), 4–5 (3).
Čuvamo niz dist[v] – najkraće do sada nađeno rastojanje od starta do v (na početku ∞, a za start 0). U svakom koraku uzimamo neobrađen čvor sa najmanjim dist: njegovo rastojanje je sigurno konačno, jer bi svaki drugi put išao preko čvora koji je već dalji. Zatim pokušavamo da skratimo put do njegovih suseda (relaksacija): ako je dist[v] + w < dist[u], onda je dist[u] = dist[v] + w.
| Korak | Uzimamo čvor | dist[1..5] posle koraka |
|---|---|---|
| početak | 0 ∞ ∞ ∞ ∞ | |
| 1 | 1 (dist 0) | 0 4 1 7 ∞ |
| 2 | 3 (dist 1) | 0 4 1 6 ∞ (1→3→4 = 6 < 7) |
| 3 | 2 (dist 4) | 0 4 1 6 ∞ (1→2→4 = 6, nije kraće) |
| 4 | 4 (dist 6) | 0 4 1 6 9 |
| 5 | 5 (dist 9) | 0 4 1 6 9 |
Najmanji dist brzo dobijamo iz reda sa prioritetom u kome su parovi (rastojanje, čvor), sa najmanjim na vrhu. Isti čvor može biti u redu više puta (svaki put kada mu se skrati rastojanje); zastarele zapise preskačemo proverom d > dist[v].
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long INF = 1e18;
int main() {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> graf(n + 1); // graf[u] = {(sused, težina)}
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graf[u].push_back({v, w});
graf[v].push_back({u, w}); // neusmeren graf
}
int s = 1;
vector<long long> dist(n + 1, INF);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, v] = pq.top();
pq.pop();
if (d > dist[v]) continue; // zastareo zapis – v je već obrađen kraćim putem
for (auto [u, w] : graf[v]) {
if (dist[v] + w < dist[u]) { // relaksacija
dist[u] = dist[v] + w;
pq.push({dist[u], u});
}
}
}
for (int v = 1; v <= n; v++) {
if (dist[v] == INF) cout << v << ": nedostizan" << endl;
else cout << v << ": " << dist[v] << endl;
}
return 0;
}
Zapis auto [d, v] = pq.top(); rastavlja par na dve promenljive (C++17). U starijim prevodiocima piše se long long d = pq.top().first; int v = pq.top().second;.
Da bismo ispisali i sam put, pri svakoj relaksaciji pamtimo odakle smo došli: pret[u] = v. Put do cilja t dobija se praćenjem pret unazad od t do starta i obrtanjem – vidi zadatak 1.
| Vrednost | |
|---|---|
| Složenost | O((n + m) log n) |
| Negativne težine | ne radi – koristi Bellman-Ford |
| Sve težine jednake | dovoljan je BFS, O(n + m) |
| Usmeren graf | radi isto – granu dodaj samo u jednom smeru |
| Graf je DAG | brže: DP po topološkom redosledu, radi i sa negativnim težinama |
Zašto ne radi sa negativnim granama: kada uzmemo čvor sa najmanjim dist, pretpostavljamo da se do njega kasnije ne može doći kraće. Negativna grana bi upravo to omogućila.
Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.
Dat je neusmeren težinski graf. Ispiši dužinu najkraćeg puta od čvora 1 do čvora n i sam put, ili -1 ako put ne postoji.
5 6
1 2 4
1 3 1
1 4 7
2 4 2
3 4 5
4 5 39
1 3 4 53 1
1 2 5-1U gradu sa n raskrsnica i m dvosmernih ulica (sa dužinama) nalazi se k bolnica. Za svaku raskrsnicu ispiši rastojanje do najbliže bolnice.
Ulaz: n m k, zatim k raskrsnica sa bolnicom, pa m ulica u v w.
5 6 2
3 5
1 2 4
1 3 1
1 4 7
2 4 2
3 4 5
4 5 31 5 0 3 0long long – zbir mnogo težina lako pređe 2·109.priority_queue je podrazumevano max-hip; za Dijkstru treba greater<…> (ili čuvaj negativna rastojanja).if (d > dist[v]) continue; program je tačan, ali može biti mnogo sporiji.1. Za koje grafove Dijkstrin algoritam daje tačan rezultat?
2. Koji čvor Dijkstra obrađuje u sledećem koraku?
3. Šta je relaksacija grane v → u težine w?
4. Koja je složenost Dijkstre sa priority_queue?
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.
Algoritam se koristi kada:
Primeri:
Za svaki čvor čuvamo udaljenost od starta. Početno stanje:
Na svakom koraku:
Relaksacija:
ako je dist[u] + w(u,v) < dist[v]:
ažuriraj dist[v]
// uključuje sve standardne biblioteke
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
// graf: lista suseda (čvor, težina)
vector<pair<int,int>> graf[100];
// niz udaljenosti
vector<int> d;
void dijkstra(int start, int n){
// inicijalizacija
d.assign(n+1, INF);
d[start] = 0;
// min-heap (udaljenost, čvor)
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, start});
while(!pq.empty()){
auto [dist, v] = pq.top();
pq.pop();
// ako je zastareo unos - preskoči
if(dist > d[v]) continue;
// prolazak kroz susede
for(auto [sused, w] : graf[v]){
if(d[v] + w < d[sused]){
d[sused] = d[v] + w;
pq.push({d[sused], sused});
}
}
}
}
int main(){
int n = 5;
// dodavanje grana
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;
}
vector<int> parent;
void dijkstra(int start, int n){
d.assign(n+1, INF);
parent.assign(n+1, -1);
d[start] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> 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; // čuvamo prethodnika
pq.push({d[sused], sused});
}
}
}
}
// vraća put od starta do cilja
vector<int> rekonstruiši_put(int cilj){
vector<int> put;
for(int v = cilj; v != -1; v = parent[v])
put.push_back(v);
reverse(put.begin(), put.end());
return put;
}
if(dist > d[v]) continue;| Struktura | Složenost |
|---|---|
| Heap | O((V + E) log V) |
| Matrica | O(V²) |
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.
Algoritam koristi se kada:
Primeri:
Za svaki čvor čuvamo udaljenost od starta. Na početku, udaljenost startnog čvora je 0, a svih ostalih je beskonačno (∞).
Na svakom koraku:
Relaksacija:
ako je dist[u] + w(u,v) < dist[v]:
onda ažuriraj dist[v]
priority_queueNajbolja 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;
}
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 << " ";
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
| Struktura | Složenost |
|---|---|
| Prioritetni red (heap) | O((V + E) log V) |
| Matrična reprezentacija | O(V²) |
Za vežbu, probaj da:
□ Nastavljamo sa minimalnim razapinjućim stablima:
Bellman-Ford i Floyd-Warshall algoritmi