Bellman-Ford i Floyd-Warshall algoritmi
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:
- negativne težine
- više potencijalnih putanja između čvorova
- potreba da se izračunaju svi parovi najkraćih puteva
Bellman-Ford algoritam
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
Primer grafa (sa negativnom težinom)
4
A --------> B
| |
| -2 | 3
| v
C <-------- D
1
Možemo imati negativne težine (npr. A → C = -2), ali ne i negativan ciklus.
Implementacija u C++
#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 algoritam
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]);
Primer matrice susedstva
Graf:
1 4
A ---> B ---> C
| ^
|______2______|
Početna matrica (INF = ∞):
A B C
A 0 1 ∞
B ∞ 0 4
C 2 ∞ 0
Implementacija u C++
#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";
}
}
Poređenje algoritama
| 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³) |
Zadaci za vežbu
- Implementirati Bellman-Ford i ispisati najkraće puteve (ne samo rastojanja).
- Primena Floyd-Warshall za rekonstrukciju putanja (držanje π matrice).
- Pronaći primer grafa gde Dijkstra daje loš rezultat, a Bellman-Ford tačan.
- Napraviti generator nasumičnih grafova i porediti brzinu algoritama.
- SIO zadatak: proveriti da li postoji negativan ciklus u grafu.
Tipične greške učenika
- Zaborave da u Bellman-Fordu provere
dist[u] < INFpre sabiranja. - U Floyd-Warshall prvo menjaju i, j petlje umesto k → neispravno rešenje.
- Negativne težine u Dijkstri → pogrešan rezultat.
- Više grana između čvorova → potrebno uzeti minimalnu.
Zaključak
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