Graf ponderat

Într-un graf ponderat, fiecare muchie sau arc are un cost. Costul unui drum este suma costurilor legăturilor parcurse. Dacă 1–2 costă 4, 2–3 costă 3, iar 1–3 costă 10, lanțul 1–2–3 costă 7 și este mai ieftin decât legătura directă de cost 10.

Într-un graf ponderat, fiecărei muchii sau fiecărui arc i se asociază un cost (pondere), de exemplu o distanță, un timp sau un preț. Costul unui drum sau al unui lanț este suma costurilor legăturilor parcurse, nu numărul lor. Un drum cu mai puține muchii nu este neapărat mai ieftin. Pe o hartă cu trei orașe, dacă 1–2 costă 4, 2–3 costă 3, iar 1–3 costă 10, lanțul 1–2–3 are două muchii și costul 7, iar muchia directă 1–3 are o muchie și costul 10.

Exemplul 1 — compararea a două trasee.

#include <iostream>
using namespace std;
int main() {
    int cost12 = 4, cost23 = 3, cost13 = 10;
    int prin2 = cost12 + cost23;
    cout << (prin2 < cost13) << " " << prin2;
}

Se afișează 1 7. Numărul de muchii și costul sunt mărimi diferite: drumul direct are o muchie, dar un cost mai mare. Lecțiile „Algoritmul Dijkstra”, „Algoritmul Roy–Floyd” și „Arbore parțial de cost minim” tratează probleme diferite: drum minim dintr-o sursă, drumuri între toate perechile și conectarea tuturor vârfurilor la cost total minim.

Exemplul 2 — matricea costurilor. În matricea costurilor, celula $(i,j)$ păstrează costul legăturii directe dintre $i$ și $j$. Absența unei legături se marchează printr-o valoare convențională de „infinit”, distinctă de costul zero, pentru că un cost 0 ar însemna o legătură gratuită. Graful neorientat are 4 vârfuri și muchiile $[1,2]$ cu 4, $[2,3]$ cu 3, $[1,3]$ cu 10 și $[3,4]$ cu 2. Programul calculează costul unui traseu dat, adunând costurile muchiilor și semnalând lipsa uneia:

#include <iostream>
using namespace std;
const int INF = 1000000;
int c[5][5];
int traseu(int v[], int k) {
    int s = 0;
    for (int i = 0; i + 1 < k; ++i) {
        if (c[v[i]][v[i + 1]] == INF) return -1;
        s += c[v[i]][v[i + 1]];
    }
    return s;
}
int main() {
    for (int i = 1; i <= 4; ++i)
        for (int j = 1; j <= 4; ++j) c[i][j] = INF;
    c[1][2] = c[2][1] = 4; c[2][3] = c[3][2] = 3;
    c[1][3] = c[3][1] = 10; c[3][4] = c[4][3] = 2;
    int a[] = {1, 2, 3, 4}, b[] = {1, 3, 4}, d[] = {1, 4};
    cout << traseu(a, 4) << " " << traseu(b, 3) << " " << traseu(d, 2);
}

Se afișează 9 12 -1. Traseul 1–2–3–4 are trei muchii și costul $4+3+2=9$. Traseul 1–3–4 are două muchii și costul $10+2=12$, deci mai puține muchii, dar un cost mai mare. Perechea $(1,4)$ nu are muchie directă, deci succesiunea 1–4 nu este lanț, iar funcția întoarce $-1$. Matricea costurilor directe nu conține încă rezultatul de drum minim 1→3, care este 7 prin 2.

Exemplul 3 — în formatul examenului. În graful din al doilea exemplu, care dintre afirmațiile despre lanțurile de la 1 la 4 este adevărată?

• a) Lanțul 1–3–4 are cost minim, 12, pentru că are cele mai puține muchii.
• b) Lanțul 1–2–3–4 are cost minim, 9, deși are mai multe muchii.
• c) Lanțul 1–2–3–4 are cost 3, egal cu numărul muchiilor.
• d) Lanțul 1–3–4 are cost 2, egal cu numărul muchiilor.

Răspunsul corect este b). Cele două lanțuri elementare de la 1 la 4 costă 9 și 12, iar minimul este 9. Variantele c) și d) confundă costul cu numărul muchiilor. Varianta a) presupune greșit că lanțul cu cele mai puține muchii este cel mai ieftin.

Exemplul 4 — graf orientat: costul depinde de sensul arcelor. Arcele sunt $1\to 2$ cu 4, $2\to 3$ cu 3 și $3\to 1$ cu 2. Drumul de la 3 la 2 este $3\to 1\to 2$ și costă $2+4=6$, pe când de la 2 la 3 se merge direct, cu costul 3. În matricea costurilor, $c[2][3]=3$, dar $c[3][2]$ rămâne „infinit”, deoarece nu există arcul $3\to 2$.

Greșeli frecvente

• Greșit: drumul cu cele mai puține muchii are mereu cost minim.
  Corect: depinde de ponderi.
• Greșit: costul drumului 1–2–3 este 4.
  Corect: este $4+3=7$.
• Greșit: un arbore parțial minim și un drum minim sunt aceeași problemă.
  Corect: au obiective diferite.

Înainte și după