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] < INF pre 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

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

← Mapa učenja — Grafovi i stabla