Modul 07 — Dijkstra: drumul de cost minim

Graful ponderat și matricea costurilor

Pe fiecare muchie — un număr: costul. În memorie: matricea costurilor, ruda matricei de adiacență.

c[i][j] = costul muchiei [i,j] dacă există · 0 pe diagonală · ∞ (o valoare uriașă) unde NU există muchie — atenție, aici 0 nu mai poate însemna „lipsă", căci un cost chiar poate fi 0!

Scenariul programei: nodul 1 = depozitul regional; nodurile 2–6 = puncte de vânzare; costurile = lei pe transport. Întrebarea: cât costă, MINIM, să ajungi din 1 în fiecare?

1const int INF = 1e9;

2int c[101][101];

3for (i...) for (j...)

4 c[i][j] = (i == j) ? 0 : INF;

5cin >> x >> y >> cost;

6c[x][y] = c[y][x] = cost;

Dijkstra pas cu pas — depozitul aprovizionează orașul

Verde = distanță FINALĂ (sigură), auriu = nodul fixat acum / distanță tocmai îmbunătățită, albastru = estimare provizorie.

d[1] = 0, restul ∞ — apasă Pas 👆

Momentele-cheie de urmărit: la pasul cu nodul 3, d[2] SCADE de la 4 la 3 — drumul 1→3→2 (1+2) bate muchia directă 1→2 (4)! Și la final, d[6] scade de la 14 la 12 prin nodul 5. Asta e „relaxarea": orice escală nouă poate ieftini o estimare.

De ce merge? Greedy cu certificat

Dijkstra alege mereu nodul nefixat cu distanța MINIMĂ — alegere lacomă (X·M12). De data asta, lăcomia e demonstrat corectă.

✔ Certificatul

Când fixezi nodul u cu cea mai mică estimare, niciun drum viitor nu-l mai poate ieftini: orice alt drum spre u trece prin noduri cu estimări ≥ d[u], iar costurile muchiilor sunt ≥ 0 — deci ar aduna, nu ar scădea. Alegerea locală nu strică viitorul: exact justificarea pe care Greedy o cerea!

✘ Limita

Cu costuri NEGATIVE, certificatul pică — un drum „mai lung" ar putea scădea totalul, iar Dijkstra dă rezultate greșite. La liceu costurile sunt ≥ 0, dar la BAC-ul teoretic întrebarea „de ce cere Dijkstra costuri nenegative?" e clasică.

Implementarea de școală — O(n²)

1for (int i = 1; i <= n; i++) d[i] = c[start][i]; // estimările inițiale

2d[start] = 0; viz[start] = 1;

3for (int pas = 1; pas < n; pas++) {

4 int u = nodul nevizitat cu d[u] MINIM; // alegerea lacomă

5 viz[u] = 1; // FIXAT definitiv

6 for (int v = 1; v <= n; v++) // relaxez vecinii

7 if (!viz[v] && d[u] + c[u][v] < d[v])

8 { d[v] = d[u] + c[u][v]; tata[v] = u; }

tata[v] memorează de unde a venit ultima îmbunătățire — mergând din tată în tată de la destinație spre start, RECONSTRUIEȘTI drumul, nu doar costul. La noi: tata[6] = 5, tata[5] = 3, tata[3] = 1 → drumul spre 6 este 1 → 3 → 5 → 6, cost 1 + 8 + 3 = 12. Verifică-l urmărind muchiile verzi din simulator!

Fișa de sinteză

Dijkstra, condensat.

Graf ponderat: costuri pe muchii; matricea costurilor cu ∞ (nu 0!) unde lipsește muchia.

Ritualul Dijkstra: fixează nodul nefixat cu d minim → relaxează-i vecinii → repetă de n−1 ori.

Relaxarea: if (d[u] + c[u][v] < d[v]) d[v] = d[u] + c[u][v] — escala nouă poate ieftini estimarea.

tata[v] = ultima escală care a îmbunătățit v → reconstruirea drumului, de la destinație înapoi.

Corectitudinea: Greedy cu certificat — valabil DOAR cu costuri ≥ 0; negative ⇒ rezultate greșite.

Rudele: BFS = Dijkstra cu toate costurile 1 · Roy-Floyd dă TOATE perechile (O(n³)), Dijkstra o sursă (O(n²)).

Urmează: fratele geamăn al lui Dijkstra — algoritmul lui Prim: nu drumuri minime, ci REȚEAUA de cost total minim care leagă toate nodurile. Aceeași lăcomie, alt obiectiv.

Cel mai ieftin drum