Algoritmul Dijkstra

Algoritmul Dijkstra găsește costurile minime de la o sursă la celelalte vârfuri când ponderile sunt nenegative. Păstrează distanțe provizorii și fixează pe rând vârful cu cea mai mică distanță cunoscută. Pentru costurile 1→2 de 2, 2→3 de 4 și 1→3 de 9, drumul prin 2 costă 6 și este mai scurt decât arcul direct.

Algoritmul lui Dijkstra determină costurile minime ale drumurilor de la o sursă la toate celelalte vârfuri ale unui graf ponderat, dacă toate costurile sunt nenegative. Variantă școlară: se folosesc matricea costurilor, vectorul distanțelor provizorii d și vectorul ales. Inițial d[s]=0, iar celelalte valori sunt infinit (o valoare convențională foarte mare). Se repetă: se alege vârful u neales cu d minim, se marchează ca ales și se actualizează fiecare vecin v prin d[v]=min(d[v],d[u]+cost[u][v]). Dacă cel mai mic d rămas este infinit, restul vârfurilor nu sunt accesibile și algoritmul se oprește. Cu matrice, timpul este $O(n^2)$, iar memoria $O(n^2)$; cu liste de adiacență și o structură de prioritate, graful rar se prelucrează în mai puțin.

Pentru arcele $1\to 2$ cu 4, $2\to 3$ cu 3 și $1\to 3$ cu 10, tabelul distanțelor pentru vârfurile 1, 2, 3 este: inițial $(0,\infty ,\infty )$; după fixarea lui 1, $(0,4,10)$; după fixarea lui 2, $(0,4,7)$; după fixarea lui 3, valorile nu se mai schimbă. Drumul direct costă 10, dar drumul prin 2 costă $4+3=7$.

Exemplul 1 — distanțe și drumul minim. Graful orientat are 5 vârfuri și arcele $1\to 2$ cu 4, $1\to 3$ cu 1, $3\to 2$ cu 2, $2\to 4$ cu 5, $3\to 4$ cu 8, $4\to 5$ cu 3. La fiecare îmbunătățire a lui d[v] se memorează tata[v]=u, ceea ce permite reconstituirea drumului:

#include <iostream>
using namespace std;
int main() {
    const int INF = 1000000, n = 5;
    int c[6][6], d[6], tata[6] = {}, ales[6] = {};
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) c[i][j] = INF;
    c[1][2] = 4; c[1][3] = 1; c[3][2] = 2;
    c[2][4] = 5; c[3][4] = 8; c[4][5] = 3;
    for (int i = 1; i <= n; ++i) d[i] = INF;
    d[1] = 0;
    for (int pas = 1; pas <= n; ++pas) {
        int u = 0;
        for (int i = 1; i <= n; ++i)
            if (!ales[i] && (u == 0 || d[i] < d[u])) u = i;
        if (d[u] == INF) break;
        ales[u] = 1;
        for (int v = 1; v <= n; ++v)
            if (c[u][v] != INF && d[u] + c[u][v] < d[v]) {
                d[v] = d[u] + c[u][v];
                tata[v] = u;
            }
    }
    for (int i = 1; i <= n; ++i) cout << d[i] << " ";
    cout << "\n";
    for (int v = 5; v; v = tata[v]) cout << v << " ";
}

Se afișează 0 3 1 8 11, apoi 5 4 2 3 1. Se fixează pe rând 1 (distanța 0), 3 (1), 2 (3, prin 3, nu prin arcul direct de cost 4), 4 (8, prin 2) și 5 (11). Predecesorii dau drumul $1\to 3\to 2\to 4\to 5$, citit invers, cu costul $1+2+5+3=11$. Valoarea 3 pentru vârful 2 a înlocuit valoarea provizorie 4, deci o distanță provizorie se poate îmbunătăți până când vârful este fixat.

Exemplul 2 — de ce nu merg ponderile negative. Corectitudinea fixării folosește ponderi nenegative: după ce u este ales, niciun ocol prin vârfuri cu distanțe cel puțin la fel de mari nu poate reduce d[u]. Cu arcele $1\to 2$ cu 2, $1\to 3$ cu 3 și $3\to 2$ cu $-2$, vârful 2 este fixat primul, cu $d=2$, dar drumul $1\to 3\to 2$ costă $3-2=1$. Algoritmul ar returna 2 în loc de 1, deci cere costuri nenegative.

Exemplul 3 — în formatul examenului. Graful neorientat are vârfurile 1, 2, 3, 4 și muchiile $[1,2]$ cu 7, $[1,3]$ cu 2, $[3,2]$ cu 3, $[2,4]$ cu 2 și $[3,4]$ cu 8. Care este costul minim al unui drum de la 1 la 4?

• a) 5
• b) 7
• c) 9
• d) 10

Răspunsul corect este b). Din 1 se fixează 3 cu $d=2$, apoi 2 cu $d=2+3=5$ (mai bun decât muchia directă de cost 7), apoi 4 cu $d=5+2=7$. Drumul este 1–3–2–4. Varianta a) este costul minim până la vârful 2, nu până la 4. Varianta c) este costul drumului 1–2–4, $7+2=9$, iar d) este costul drumului 1–3–4, $2+8=10$.

Greșeli frecvente

• Greșit: Dijkstra funcționează neschimbat cu ponderi negative.
  Corect: cere ponderi nenegative.
• Greșit: distanța 1→3 este 10 deoarece există arc direct.
  Corect: drumul prin 2 costă 7.
• Greșit: o distanță provizorie nu se mai poate îmbunătăți.
  Corect: se poate reduce până când vârful este fixat.

Înainte și după