Bellman–Ford: costuri negative și drumuri minime

Bellman–Ford calculează drumuri de cost minim de la o sursă într-un graf orientat care poate avea arce cu cost negativ. Algoritmul detectează și existența unui ciclu negativ accesibil din sursă, situație în care unele distanțe nu mai au un minim finit.

Un arc negativ nu este singur o problemă. Dificultatea apare când putem parcurge repetat un ciclu cu sumă negativă, reducând costul de fiecare dată. Sursa și accesibilitatea contează: un ciclu aflat într-o zonă inaccesibilă nu influențează drumurile pornite din sursa aleasă.

Cum funcționează

Inițial, sursa are distanța zero, iar celelalte vârfuri INF. Relaxarea arcului u→v verifică dacă un drum cunoscut până la u, urmat de acel arc, îmbunătățește distanța lui v. Nu relaxăm dintr-un vârf încă inaccesibil, deoarece INF este un marcaj, nu un cost care trebuie adunat.

Executăm cel mult n-1 treceri peste toate arcele. În absența ciclurilor negative accesibile, există drumuri optime simple, deci cu cel mult n-1 arce. După suficiente treceri, toate aceste drumuri au fost luate în calcul. Actualizările în aceeași trecere pot propaga informația mai repede, dar argumentul celor n-1 treceri rămâne o limită sigură.

O trecere fără modificări permite oprirea timpurie. După faza principală, verificăm încă o dată dacă vreun arc accesibil mai poate fi relaxat. Dacă da, există un ciclu negativ accesibil. Programul afișează un mesaj global și se oprește; nu încearcă să clasifice separat fiecare vârf afectat. Pentru acea variantă trebuie propagate efectele către toate vârfurile accesibile din ciclurile detectate.

Limitele sunt 1 <= n <= 100, 0 <= m <= 10000 și costuri cu modulul cel mult un milion. Lista clasică are capacitatea 10000, distanțele folosesc indicii 1..n, iar long long oferă spațiu pentru relaxările din aceste limite. Varianta vector păstrează exact aceiași pași și aceeași convenție pentru INF.

Exemplu urmărit pas cu pas

Pentru 1→2 cu cost 4, 1→3 cu cost 5 și 2→3 cu cost -2, distanța minimă 1→3 este 2. Alegerea definitivă a unui vârf pe baza unei distanțe provizorii cere condiții pe care Dijkstra le asigură numai pentru costuri nenegative; Bellman–Ford permite îmbunătățiri repetate.

Dacă adăugăm 3→2 cu cost 1, ciclul 2→3→2 costă -1. El este accesibil din 1 și poate fi repetat oricât, deci distanțele spre 2 și 3 nu au minime finite. Un vârf complet separat poate rămâne totuși inaccesibil.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
struct Edge {
    int u, v;
    long long w;
};
int main() {
    int n, m, s;
    std::cin >> n >> m >> s;
    Edge edges[10000];
    long long d[101];
    for (int i = 0; i < m; ++i)
        std::cin >> edges[i].u >> edges[i].v >> edges[i].w;
    const long long INF = 4000000000000000000LL;
    for (int i = 1; i <= n; ++i)
        d[i] = INF;
    d[s] = 0;
    for (int pass = 1; pass < n; ++pass) {
        bool changed = false;
        for (int i = 0; i < m; ++i) {
            auto e = edges[i];
            if (d[e.u] != INF && d[e.v] > d[e.u] + e.w) {
                d[e.v] = d[e.u] + e.w;
                changed = true;
            }
        }
        if (!changed)
            break;
    }
    bool negative = false;
    for (int i = 0; i < m; ++i) {
        auto e = edges[i];
        if (d[e.u] != INF && d[e.v] > d[e.u] + e.w)
            negative = true;
    }
    if (negative) {
        std::cout << "CICLU NEGATIV ACCESIBIL\n";
        return 0;
    }
    for (int i = 1; i <= n; ++i) {
        if (d[i] == INF)
            std::cout << "INF";
        else
            std::cout << d[i];
        std::cout << (i == n ? '\n' : ' ');
    }
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
struct Edge {
    int u, v;
    long long w;
};
int main() {
    int n, m, s;
    std::cin >> n >> m >> s;
    std::vector<Edge> edges(m);
    std::vector<long long> d(n + 1);
    for (int i = 0; i < m; ++i)
        std::cin >> edges[i].u >> edges[i].v >> edges[i].w;
    const long long INF = 4000000000000000000LL;
    for (int i = 1; i <= n; ++i)
        d[i] = INF;
    d[s] = 0;
    for (int pass = 1; pass < n; ++pass) {
        bool changed = false;
        for (int i = 0; i < m; ++i) {
            auto e = edges[i];
            if (d[e.u] != INF && d[e.v] > d[e.u] + e.w) {
                d[e.v] = d[e.u] + e.w;
                changed = true;
            }
        }
        if (!changed)
            break;
    }
    bool negative = false;
    for (int i = 0; i < m; ++i) {
        auto e = edges[i];
        if (d[e.u] != INF && d[e.v] > d[e.u] + e.w)
            negative = true;
    }
    if (negative) {
        std::cout << "CICLU NEGATIV ACCESIBIL\n";
        return 0;
    }
    for (int i = 1; i <= n; ++i) {
        if (d[i] == INF)
            std::cout << "INF";
        else
            std::cout << d[i];
        std::cout << (i == n ? '\n' : ' ');
    }
}

De ce funcționează și cât costă

După k treceri, sunt acoperite cel puțin drumurile cu cel mult k arce. Un drum simplu are maximum n-1 arce. O îmbunătățire suplimentară accesibilă indică necesitatea unui ciclu care reduce costul, deci a unui ciclu negativ.

Timpul nefavorabil este O(nm), iar memoria O(n+m) pentru lista de arce și distanțe. Oprirea timpurie ajută unele intrări, dar nu schimbă limita nefavorabilă. Pentru grafuri mari cu costuri nenegative, Dijkstra poate fi preferabil.

Greșeli frecvente

Nu raporta orice ciclu drept negativ și nu ignora condiția de accesibilitate. Nu afișa distanțele provizorii ca minime finite când detectezi un ciclu negativ. Nu folosi -1 pentru inaccesibil dacă -1 poate fi un cost valid.

Exersează

Un ciclu negativ este accesibil din sursă, dar din el nu există drum către vârful t. Este obligatoriu ca distanța lui t să fie afectată?

Rezolvare explicată: Nu. Costul poate scădea fără limită numai pentru destinații la care se poate ajunge după parcurgerea ciclului. Trebuie analizată accesibilitatea din ciclu spre t.

Continuă să înveți

Dijkstra, Floyd și conexitate.

Întrebări frecvente

Un arc negativ înseamnă automat ciclu negativ?

Nu. Un arc poate avea cost negativ fără să existe un drum de întoarcere. Contează suma costurilor pe un ciclu complet.

De ce facem n-1 treceri?

În absența ciclurilor negative relevante, un drum optim poate fi ales simplu și are cel mult n-1 arce. Fiecare trecere acoperă cel puțin încă un arc în argumentul de corectitudine.

Ce se întâmplă cu un ciclu negativ inaccesibil?

Nu afectează drumurile din sursa aleasă. Verificarea d[u]!=INF împiedică relaxările pornite dintr-o zonă inaccesibilă.

Toate vârfurile au distanțe nedefinite când există un ciclu negativ?

Nu. Sunt afectate cele accesibile dintr-un asemenea ciclu accesibil din sursă. Exemplul raportează existența globală și nu face această clasificare detaliată.

Pot folosi Dijkstra dacă există doar un arc negativ?

Garanția obișnuită a lui Dijkstra cere toate costurile nenegative. Numărul mic de arce negative nu înlocuiește această condiție.