Dijkstra în C++: drumuri de cost minim

Dijkstra calculează distanțele minime de la o sursă într-un graf ale cărui costuri sunt nenegative. Spre deosebire de BFS, urmărește suma costurilor, nu numărul muchiilor. Un drum cu mai multe arce poate fi mai ieftin decât unul direct.

Condiția costurilor nenegative este parte din corectitudinea metodei. Dacă există arce negative, simpla schimbare a unui tip numeric nu repară algoritmul; trebuie ales un algoritm potrivit acelei situații.

Cum funcționează

Menținem distanțe provizorii d și o mulțime de vârfuri finalizate. Sursa are distanța zero, celelalte pornesc de la o valoare INF care înseamnă inaccesibil încă. La fiecare pas alegem vârful nefinalizat cu distanța cea mai mică.

După alegere, relaxăm arcele sale: dacă traseul prin x oferă d[x]+cost(x,y) mai mic decât d[y], actualizăm d[y]. Relaxarea compară o soluție cunoscută cu o alternativă concretă. Dacă vrem și traseul, memorăm părintele y=x la fiecare îmbunătățire și reconstruim ulterior de la destinație.

Exemplul folosește o matrice de costuri și o căutare liniară a minimului. Presupunem 1 <= n <= 100, costuri între zero și un miliard și vârfuri valide. Pentru arce repetate păstrăm costul minim. Absența unui arc este reprezentată prin INF, nu prin zero, fiindcă zero este un cost permis.

În grafuri mari și rare, listele de adiacență și un heap de priorități reduc costul practic. Când o implementare introduce mai multe intrări pentru același vârf în heap, trebuie să ignore intrările depășite, altfel poate prelucra inutil aceeași stare.

Exemplu urmărit pas cu pas

Avem 1→2 cu cost 10, 1→3 cu cost 2 și 3→2 cu cost 3. După sursa 1, distanțele provizorii sunt 10 către 2 și 2 către 3. Alegem 3, iar relaxarea lui 3→2 reduce distanța la 5. Abia apoi finalizăm 2.

BFS ar prefera arcul direct către 2 dacă ar minimiza numărul de arce, dar costul 10 este mai mare decât 2+3. Un vârf fără traseu din sursă păstrează INF și este afișat ca -1 în convenția programului.

Implementare C++17

Varianta cu tablou clasic:

#include <algorithm>
#include <iostream>
int main() {
    int n, m, s;
    std::cin >> n >> m >> s;
    const long long INF = 4000000000000000000LL;
    long long a[101][101], d[101];
    bool used[101] = {};
    for (int i = 1; i <= n; ++i) {
        d[i] = INF;
        for (int j = 1; j <= n; ++j)
            a[i][j] = INF;
    }
    for (int k = 0; k < m; ++k) {
        int x, y;
        long long w;
        std::cin >> x >> y >> w;
        a[x][y] = std::min(a[x][y], w);
    }
    d[s] = 0;
    for (int step = 0; step < n; ++step) {
        int x = -1;
        for (int i = 1; i <= n; ++i)
            if (!used[i] && (x == -1 || d[i] < d[x]))
                x = i;
        if (x == -1 || d[x] == INF) {
            break;
        }
        used[x] = true;
        for (int y = 1; y <= n; ++y)
            if (a[x][y] != INF && d[x] + a[x][y] < d[y])
                d[y] = d[x] + a[x][y];
    }
    for (int i = 1; i <= n; ++i)
        std::cout << (d[i] == INF ? -1 : d[i]) << (i == n ? '\n' : ' ');
}

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

#include <algorithm>
#include <iostream>
#include <vector>
int main() {
    int n, m, s;
    std::cin >> n >> m >> s;
    const long long INF = 4000000000000000000LL;
    std::vector<std::vector<long long>> a(n + 1, std::vector<long long>(n + 1));
    std::vector<long long> d(n + 1);
    std::vector<char> used(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        d[i] = INF;
        for (int j = 1; j <= n; ++j)
            a[i][j] = INF;
    }
    for (int k = 0; k < m; ++k) {
        int x, y;
        long long w;
        std::cin >> x >> y >> w;
        a[x][y] = std::min(a[x][y], w);
    }
    d[s] = 0;
    for (int step = 0; step < n; ++step) {
        int x = -1;
        for (int i = 1; i <= n; ++i)
            if (!used[i] && (x == -1 || d[i] < d[x]))
                x = i;
        if (x == -1 || d[x] == INF) {
            break;
        }
        used[x] = true;
        for (int y = 1; y <= n; ++y)
            if (a[x][y] != INF && d[x] + a[x][y] < d[y])
                d[y] = d[x] + a[x][y];
    }
    for (int i = 1; i <= n; ++i)
        std::cout << (d[i] == INF ? -1 : d[i]) << (i == n ? '\n' : ' ');
}

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

Când alegem minimul provizoriu x, orice traseu alternativ printr-un vârf încă nefinalizat ar adăuga costuri nenegative unei distanțe cel puțin la fel de mari. Nu poate produce o cale mai scurtă spre x. Acesta este motivul finalizării sigure.

Varianta cu matrice costă O(n²) timp și memorie. Un heap împreună cu liste conduce la limite de tip O((n+m) log n) pentru implementările uzuale. INF trebuie să depășească toate distanțele valide și adunările trebuie protejate.

Greșeli frecvente

Nu aduna un cost la INF și nu folosi zero pentru arc absent. Nu aplica Dijkstra pe arce negative. Pentru grafuri neorientate, înscrie fiecare muchie în ambele sensuri, păstrând aceeași convenție de cost.

Exersează

Adaugă arcul 2→4 cu cost 1 în exemplul lecției. Care este costul minim până la 4 și ce traseu îl obține?

Rezolvare explicată: Costul este șase, prin 1→3→2→4: 2+3+1. Traseul 1→2→4 costă unsprezece, deși folosește mai puține arce.

Continuă să înveți

BFS, drumuri și greedy.

Întrebări frecvente

De ce BFS nu înlocuiește Dijkstra?

BFS minimizează numărul arcelor când toate au același cost. Dijkstra compară sumele costurilor nenegative și poate alege un traseu cu mai multe arce.

Sunt permise costuri zero?

Da. Dijkstra cere costuri nenegative, deci zero este valid. Tocmai de aceea absența unui arc trebuie reprezentată prin altă valoare.

Ce fac dacă există un arc negativ?

Nu mai poți folosi demonstrația standard a finalizării. În funcție de problemă, alegi Bellman–Ford, o ordine topologică pentru DAG sau altă metodă adecvată.

Cum aflu traseul, nu doar costul?

Păstrezi părintele la fiecare relaxare reușită. După terminare, urmărești părinții de la destinație spre sursă și inversezi ordinea.

Ce înseamnă un vârf inaccesibil?

Nu există niciun drum orientat din sursa aleasă până la el. Distanța rămâne INF și trebuie afișată conform convenției cerute de enunț.