Dva algoritma za najkraće puteve koji rade i sa negativnim težinama: Bellman-Ford nalazi rastojanja od jednog čvora i otkriva negativne cikluse, a Floyd-Warshall u tri ugnježdene petlje računa rastojanja između svih parova čvorova.
Najkraći put bez ciklusa ima najviše n − 1 granu. Zato je dovoljno n − 1 puta proći kroz sve grane i relaksirati svaku: posle k-tog prolaza tačna su sva rastojanja do kojih se stiže sa najviše k grana.
Ako se i u n-tom prolazu neko rastojanje smanji, postoji negativan ciklus dostižan iz starta – njime se put može skraćivati beskonačno.
#include <iostream>
#include <vector>
using namespace std;
const long long INF = 1e18;
struct Grana { int u, v, w; };
int main() {
int n, m;
cin >> n >> m;
vector<Grana> g(m);
for (auto &e : g) cin >> e.u >> e.v >> e.w; // usmerene grane u -> v
vector<long long> dist(n + 1, INF);
dist[1] = 0;
for (int prolaz = 1; prolaz <= n - 1; prolaz++)
for (auto &e : g)
if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
dist[e.v] = dist[e.u] + e.w;
// n-ti prolaz: ako se još nešto skraćuje, postoji negativan ciklus
for (auto &e : g)
if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
cout << "NEGATIVAN CIKLUS" << endl;
return 0;
}
for (int v = 1; v <= n; v++) {
if (dist[v] == INF) cout << "INF ";
else cout << dist[v] << " ";
}
cout << endl;
return 0;
}
Provera dist[e.u] != INF je važna: bez nje bi „∞ + negativna težina“ izgledalo kao skraćenje. Složenost je O(n · m) – sporije od Dijkstre, ali radi sa negativnim granama.
Matrica d[i][j] na početku sadrži težinu grane i → j (ili ∞, a d[i][i] = 0). Zatim za svaki čvor k proveravamo da li je put i → k → j kraći od dosadašnjeg i → j. Posle obrade čvora k matrica sadrži najkraće puteve koji kao međučvorove koriste samo čvorove 1..k.
#include <iostream>
#include <algorithm>
using namespace std;
const long long INF = 1e18;
long long d[401][401];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = (i == j) ? 0 : INF;
for (int i = 0; i < m; i++) {
int u, v;
long long w;
cin >> u >> v >> w;
d[u][v] = min(d[u][v], w); // može biti više grana između istih čvorova
}
for (int k = 1; k <= n; k++) // k mora biti SPOLJNA petlja
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (d[i][k] != INF && d[k][j] != INF)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (d[i][j] == INF) cout << "INF";
else cout << d[i][j];
cout << (j < n ? " " : "\n");
}
}
return 0;
}
Složenost O(n³) – za n ≤ 400–500. Ako je posle algoritma neki d[i][i] < 0, čvor i je na negativnom ciklusu.
| Algoritam | Od koga | Negativne težine | Složenost | Kada |
|---|---|---|---|---|
| BFS | jedan čvor | – | O(n + m) | sve grane iste dužine |
| Dijkstra | jedan čvor | ne | O((n + m) log n) | najčešći slučaj |
| Bellman-Ford | jedan čvor | da, otkriva negativne cikluse | O(n · m) | negativne grane, n·m ≤ ~108 |
| Floyd-Warshall | svi parovi | da | O(n³) | mali graf, mnogo upita |
| DP na DAG-u | jedan čvor | da | O(n + m) | graf bez ciklusa |
Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.
Dato je n ≤ 300 gradova i m dvosmernih puteva sa dužinama, zatim q upita a b. Za svaki upit ispiši dužinu najkraćeg puta, ili -1 ako put ne postoji.
4 3
1 2 5
2 3 2
1 3 9
3
1 3
3 1
1 47
7
-1Menjačnica ima n valuta i m kurseva oblika a b c: zamena valute a za b „košta“ c poena (c može biti negativno – tada se dobija). Da li postoji niz zamena koji počinje i završava se istom valutom, a ukupno donosi dobitak (zbir manji od 0)? Ispiši DA ili NE.
3 3
1 2 1
2 3 -2
3 1 0DA3 3
1 2 1
2 3 -1
3 1 1NEdist = ∞.k mora biti spoljašnja.1. Koliko prolaza kroz sve grane je dovoljno Bellman-Fordu ako nema negativnog ciklusa?
2. Kako Bellman-Ford otkriva negativan ciklus?
3. Koja je složenost Floyd-Warshalla?
U ovoj lekciji obrađujemo dva važna algoritma za najkraće puteve u grafovima: Bellman-Ford i Floyd-Warshall.
Za razliku od Dijkstre, ovi algoritmi mogu raditi i kada postoje:
Bellman-Ford pronalazi najkraće puteve od jednog izvorišnog čvora do svih ostalih. Radi i u prisustvu negativnih težina, ali ne sme biti negativnih ciklusa.
Ideja: relaksiramo sve grane grafa (V - 1) puta. Ako se nakon toga neka udaljenost i dalje poboljšava → postoji negativan ciklus.
// Pseudokod:
dist[s] = 0, ostali INF
Ponovi (V-1) puta:
za svaku granu (u, v, w):
ako dist[u] + w < dist[v]:
dist[v] = dist[u] + w
Provera negativnog ciklusa:
za svaku granu (u, v, w):
ako dist[u] + w < dist[v]:
postoji negativan ciklus
4
A --------> B
| |
| -2 | 3
| v
C <-------- D
1
Možemo imati negativne težine (npr. A → C = -2), ali ne i negativan ciklus.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main(){
int n, m, s;
cin >> n >> m >> s;
vector<tuple<int,int,int>> edges;
for(int i=0;i<m;i++){
int u,v,w;
cin >> u >> v >> w;
edges.push_back({u,v,w});
}
vector<int> dist(n+1, INF);
dist[s] = 0;
// (n-1) relaksacija
for(int i=1;i<n;i++){
for(auto &e : edges){
auto [u,v,w] = e;
if(dist[u] < INF && dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
}
}
}
// Provera negativnog ciklusa
for(auto &e : edges){
auto [u,v,w] = e;
if(dist[u] < INF && dist[u] + w < dist[v]){
cout << "NEGATIVAN CIKLUS!\n";
return 0;
}
}
for(int i=1;i<=n;i++){
cout << "dist do " << i << " = " << dist[i] << "\n";
}
}
Floyd-Warshall računa najkraće rastojanje između svih parova čvorova. Koristi se za grafove sa do ~400 čvorova (zbog O(n³) vremena).
Može detektovati negativne cikluse ako dist[i][i] < 0.
// Osnovna ideja:
Za svaki čvor k:
za svaki čvor i:
za svaki čvor j:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
Graf:
1 4
A ---> B ---> C
| ^
|______2______|
Početna matrica (INF = ∞):
A B C
A 0 1 ∞
B ∞ 0 4
C 2 ∞ 0
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main(){
int n, m;
cin >> n >> m;
vector<vector<int>> dist(n+1, vector<int>(n+1, INF));
for(int i=1;i<=n;i++) dist[i][i] = 0;
for(int i=0;i<m;i++){
int u,v,w;
cin >> u >> v >> w;
dist[u][v] = min(dist[u][v], w); // ako više grana - uzmi manju
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dist[i][k] < INF && dist[k][j] < INF)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
// Detekcija negativnih ciklusa
for(int i=1;i<=n;i++){
if(dist[i][i] < 0){
cout << "NEGATIVAN CIKLUS!\n";
return 0;
}
}
// Ispis
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dist[i][j] == INF) cout << "INF ";
else cout << dist[i][j] << " ";
}
cout << "\n";
}
}
| Algoritam | Primena | Negativne težine? | Složenost |
|---|---|---|---|
| Dijkstra | Najkraći put od jednog čvora | NE | O((V+E) log V) |
| Bellman-Ford | Najkraći put od jednog čvora | DA | O(V * E) |
| Floyd-Warshall | Svi parovi čvorova | DA | O(V³) |
dist[u] < INF pre sabiranja.Bellman-Ford i Floyd-Warshall su ključni algoritmi za takmičenja, posebno kada graf sadrži negativne težine ili kada treba naći najkraće puteve između svih parova čvorova.
□ Preporučeno sledeće za učenje: MST - Primov algoritam