Graf ponderat

Ce este

Un graf obișnuit îți spune doar cine e vecin cu cine: există muchie sau nu. Dar în viața reală o legătură are aproape mereu un preț — distanță, timp, bani, lățime de bandă. Un graf ponderat adaugă exact această informație: fiecărei muchii (la grafuri orientate: fiecărui arc) i se asociază un număr numit pondere sau cost, notat w(u, v) — citește „weight de la u la v". Întrebarea nu mai e „pot ajunge de la A la B?", ci „cât mă costă cel mai ieftin drum de la A la B?".

Două noțiuni decurg imediat:

• Costul unui lanț (drum) este suma ponderilor muchiilor pe care le parcurge. Un drum care trece prin muchiile de cost 3, 5 și 1 are costul 3 + 5 + 1 = 9.
• Drumul de cost minim între două noduri este cel cu suma cea mai mică — nu neapărat cel cu cele mai puține muchii.

Ponderea poate însemna orice măsură numerică a legăturii: kilometri, minute, lei, capacitate. Iar valorile pot fi și negative (ex. un câștig pe o tranzacție), ceea ce schimbă ce algoritm ai voie să folosești mai târziu.

Cum arată

Mai jos ai un graf neorientat cu 6 noduri în care fiecare muchie poartă un cost. Construiește-l muchie cu muchie și urmărește numărul scris pe fiecare legătură — aceea e ponderea ei. Observă că o muchie ponderată e descrisă de trei lucruri, nu două: capătul stâng, capătul drept și costul dintre ele.

Iată muchiile grafului implicit din vizualizare, fiecare cu costul ei (u — v : cost):

0 — 1 : 4, 0 — 2 : 3, 1 — 3 : 2, 2 — 3 : 5, 3 — 4 : 1, 4 — 5 : 6, 2 — 5 : 7.

Vrem să mergem de la nodul 0 la nodul 4. Există mai multe drumuri, iar ele nu costă la fel. Compară două dintre ele:

Observă esențialul: ambele drumuri au același număr de muchii (trei), dar costuri diferite (9 față de 7). Într-un graf neponderat ar fi fost „la fel de buni"; aici al doilea câștigă. De asta ponderile schimbă complet jocul.

Implementare C++

Reprezentăm graful ponderat cu liste de adiacență de perechi: pentru fiecare nod ținem lista vecinilor lui împreună cu costul muchiei către ei — adică perechi (vecin, cost). Programul citește muchiile ponderate, apoi calculează costul total al unui drum dat ca șir de noduri.

#include <iostream>
#include <vector>
using namespace std;

// pereche (vecin, cost) pentru fiecare muchie din lista de adiacenta
vector<pair<int, int>> adj[105];

int main() {
    int n, m;            // n = noduri, m = muchii
    cin >> n >> m;
    for (int e = 0; e < m; e++) {
        int u, v, w;     // capat u, capat v, ponderea w
        cin >> u >> v >> w;
        // graf neorientat: stocam costul in ambele sensuri
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // citim un drum dat ca sir de k noduri: nod_1 nod_2 ... nod_k
    int k;
    cin >> k;
    vector<int> drum(k);
    for (int i = 0; i < k; i++) cin >> drum[i];

    // costul drumului = suma ponderilor muchiilor consecutive
    long long cost = 0;  // long long: multe muchii mari pot depasi int
    for (int i = 0; i + 1 < k; i++) {
        int a = drum[i], b = drum[i + 1];
        // cautam costul muchiei a-b in lista de adiacenta a lui a
        int w_ab = -1;
        for (auto vecin : adj[a]) {
            if (vecin.first == b) { w_ab = vecin.second; break; }
        }
        cost += w_ab;    // daca w_ab a ramas -1, muchia nu exista
    }

    cout << cost << "\n";   // pentru drumul 0 1 3 4 afiseaza 7
    return 0;
}

Cheia este că în listă stocăm pair<int, int> — vecinul și costul împreună. Dacă am ține doar vecinul (ca la un graf neponderat), informația de pondere s-ar pierde și n-am mai putea aduna nimic.

Pentru grafuri mici sau dense poți folosi și matricea de costuri: cost[u][v] = ponderea muchiei u — v. Atenție însă la ce pui acolo unde muchia nu există — nu 0, ci o valoare „infinit" (de exemplu constanta INF = 1e9), altfel lipsa muchiei devine muchie gratuită.