SISergiu Ilincameditații informatică
Meniu

clasa a XI-a · Grafuri · lecția 19

Grafuri cu costuri: Dijkstra, Roy-Floyd, arbori parțiali de cost minim (Prim, Kruskal)

60 minintensiv informatică / olimpiadăintensiv

Înainte de lecția asta: XI.12 Grafuri orientate: arce, grade, drumuri, circuite, tare conexitate, XI.13 Arbori: definiție, arbori cu rădăcină, vectorul de tați

Ce vei ști după lecție

  • Reprezinți un graf cu costuri prin matricea costurilor.
  • Calculezi drumurile minime de la un nod la toate celelalte (Dijkstra).
  • Calculezi drumurile minime între oricare două noduri (Roy-Floyd).
  • Construiești arborele parțial de cost minim (Prim, Kruskal).

Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓

Clasa a XI-aLecția 19 din 21 · mai sunt 2Urmează: XI.20 · Arbori binari și arbori binari de căutareVezi toate lecțiile
Cuprins

Fișiere PDF și de lucru

1. Graf cu costuri

Până acum o muchie spunea doar „există drum”. Acum fiecare muchie are un cost: kilometri, minute, lei. Întrebările devin: care este drumul cel mai ieftin? cum conectăm toate orașele cu cabluri cât mai ieftin?

Graf cu costuri

Se memorează în matricea costurilor: c[i][j] = costul muchiei (i, j); 0 pe diagonală; INF (o valoare foarte mare, de exemplu 10⁹) dacă muchia nu există.

const int INF = 1000000000;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        c[i][j] = (i == j) ? 0 : INF;
// la citirea muchiei (x, y) cu costul z:  c[x][y] = c[y][x] = z;   (orientat: doar c[x][y] = z)

De ce așa?

De ce INF și nu 0 pentru „nu există muchie”? Zero ar însemna „muchie gratuită”, iar algoritmii ar folosi muchii inexistente. INF este „atât de scump încât nu merită niciodată”. De ce 10⁹ și nu cel mai mare int? Când aduni două costuri INF + INF depășești int și obții un număr negativ (depășire); 10⁹ + 10⁹ = 2·10⁹ încape încă în int (limita este ~2,1·10⁹), dar adună cu grijă.

2. Dijkstra: drumuri minime dintr-un nod (costuri ≥ 0)

Ideea. Imaginează-te la nodul de start. Distanța până la el este 0. Pornești „un val”: la fiecare pas alegi nodul nefixat cu distanța cea mai mică. Distanța lui este definitivă (orice alt drum ar trece prin noduri mai depărtate și ar fi mai lung), apoi vezi dacă prin el poți ajunge mai ieftin la vecinii lui.

Pe graful de mai sus, din nodul 1:

Dijkstra

Pas Nod fixat Ce se îmbunătățește
1 1 (d = 0) d[2] = 7, d[3] = 9, d[6] = 14
2 2 (d = 7) d[4] = 7 + 15 = 22 (3 rămâne 9, fiindcă 7 + 10 = 17 e mai mult)
3 3 (d = 9) d[4] = 9 + 11 = 20 (mai bine decât 22); d[6] = 9 + 2 = 11 (mai bine decât 14)
4 6 (d = 11) d[5] = 11 + 9 = 20
5 4 (d = 20) nimic nou
6 5 (d = 20) nimic nou

Arborele drumurilor

#include <iostream>
using namespace std;

const int INF = 1000000000;
int n, m, s, c[101][101], d[101];
bool viz[101];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            c[i][j] = (i == j) ? 0 : INF;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        c[x][y] = c[y][x] = z;
    }
    cin >> s;
    for (int i = 1; i <= n; i++) d[i] = c[s][i];   // distanțe inițiale: doar muchiile directe
    viz[s] = true;
    for (int pas = 1; pas < n; pas++)
    {
        int mn = INF, x = 0;
        for (int i = 1; i <= n; i++)               // nodul nefixat cu d minim
            if (!viz[i] && d[i] < mn) { mn = d[i]; x = i; }
        if (x == 0) break;                         // restul sunt inaccesibile
        viz[x] = true;
        for (int y = 1; y <= n; y++)               // îmbunătățim vecinii
            if (!viz[y] && c[x][y] < INF && d[x] + c[x][y] < d[y])
                d[y] = d[x] + c[x][y];
    }
    for (int i = 1; i <= n; i++) cout << d[i] << ' ';
    return 0;
}

De ce așa?

De ce nodul cu d minim este definitiv? Orice alt drum spre el ar trece prin cel puțin un nod nefixat, iar toate au distanțe ≥ d minim; cum costurile nu sunt negative, drumul alternativ nu poate fi mai scurt. De ce nu merge cu costuri negative? Exact acest argument cade: un cost negativ poate „răscumpăra” un ocol.

Cost negativ

Complexitate: O(n²) (n pași, fiecare cu două parcurgeri de n). Bun pentru n ≤ 2000–3000.

De știut

Cum obții și drumul, nu doar costul? Păstrează tata[y] = x de fiecare dată când îmbunătățești d[y] prin x. Apoi reconstruiești de la destinație spre start (ca la Lee, lecția XI.17).

3. Roy-Floyd: drumuri minime între oricare două noduri

Ideea. Pentru fiecare nod k, întrebăm: „pot ajunge de la i la j mai ieftin trecând prin k?”. Dacă da, actualizăm. După ce am încercat toți k, matricea conține distanțele minime între toate perechile.

Roy-Floyd

Exemplu: de la 1 la 3 nu exista arc direct (∞). Prin nodul 2: 3 + 2 = 5. Deci c[1][3] = 5.

#include <iostream>
using namespace std;

const int INF = 1000000000;
int n, m, c[101][101];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            c[i][j] = (i == j) ? 0 : INF;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        c[x][y] = z;                                // graf orientat
    }
    for (int k = 1; k <= n; k++)                    // nodul intermediar: cel mai exterior!
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (c[i][k] < INF && c[k][j] < INF && c[i][k] + c[k][j] < c[i][j])
                    c[i][j] = c[i][k] + c[k][j];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++) cout << c[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}

De ce așa?

De ce k este bucla exterioară? După ce ai terminat pasul k, c[i][j] este cel mai bun drum care folosește ca intermediare doar nodurile 1…k. Dacă inversezi ordinea buclelor, această proprietate se pierde și răspunsul poate fi greșit (o greșeală foarte frecventă). De ce testul < INF? Fără el aduni INF + ceva și poți „îmbunătăți” o valoare cu un drum care nu există.

Complexitate O(n³): n ≤ 200–400. Dijkstra de la fiecare nod ar costa tot n · n² = n³, dar Floyd are cod mult mai scurt.

4. Arbore parțial de cost minim (APM)

Un orășel are n localități și vrea să le lege cu cabluri; fiecare legătură posibilă are un preț. Vrem conectarea tuturor cu costul total minim. Soluția are n − 1 muchii (un arbore: mai puține nu conectează, mai multe închid cicluri inutile și scumpe).

APM

Kruskal: muchiile cele mai ieftine primele

Sortezi muchiile după cost și le iei pe rând, dar doar dacă nu închid un ciclu (adică leagă două componente diferite).

Kruskal

Pas Muchie (cost) Componente înainte Decizie
1 3–6 (2) {3}, {6} ia
2 4–5 (6) {4}, {5} ia
3 1–2 (7) {1}, {2} ia
4 1–3 (9) {1,2}, {3,6} ia
5 5–6 (9) {4,5}, {1,2,3,6} ia (5 muchii: gata)
6 2–3 (10) aceeași componentă respinsă (ciclu)
#include <iostream>
#include <algorithm>
using namespace std;

struct muchie { int x, y, cost; };
muchie e[10001];
int n, m, comp[101];

bool cmp(muchie a, muchie b) { return a.cost < b.cost; }

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> e[i].x >> e[i].y >> e[i].cost;
    sort(e, e + m, cmp);                            // crescător după cost
    for (int i = 1; i <= n; i++) comp[i] = i;       // fiecare nod: componenta lui
    int total = 0, luate = 0;
    for (int k = 0; k < m && luate < n - 1; k++)
        if (comp[e[k].x] != comp[e[k].y])           // componente diferite → nu face ciclu
        {
            total += e[k].cost;
            luate++;
            int vechi = comp[e[k].y], nou = comp[e[k].x];
            for (int i = 1; i <= n; i++)            // unim componentele
                if (comp[i] == vechi) comp[i] = nou;
        }
    cout << total;
    return 0;
}

De ce așa?

De ce greedy (alegerea celei mai ieftine muchii) dă optimul aici, dar nu la monede (lecția XI.15)? Pentru APM se demonstrează că cea mai ieftină muchie care nu închide ciclu poate fi inclusă întotdeauna într-o soluție optimă („proprietatea de tăiere”). La monede nu există o astfel de garanție. De ce comp[x] != comp[y] înseamnă „fără ciclu”? O muchie între două noduri din aceeași componentă ar crea un al doilea drum între ele, deci un ciclu.

Complexitate: sortarea O(m log m) + unirile O(n · n). Cu păduri de mulțimi disjuncte (DSU) unirile devin aproape O(1) (vezi „Mai departe”).

Prim: arborele crește dintr-un nod

Pornești cu nodul 1. La fiecare pas adaugi cea mai ieftină muchie care leagă arborele de un nod din afara lui. Pe graful nostru: 1–2 (7), 1–3 (9), 3–6 (2), 6–5 (9), 5–4 (6): total 33, la fel ca Kruskal (APM-ul poate diferi la costuri egale, dar costul total este același).

Algoritmul seamănă cu Dijkstra: d[i] = cel mai ieftin cost al unei muchii care leagă nodul i de arbore.

#include <iostream>
using namespace std;

const int INF = 1000000000;
int n, m, c[101][101], d[101];
bool inArbore[101];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            c[i][j] = INF;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        c[x][y] = c[y][x] = z;
    }
    for (int i = 1; i <= n; i++) d[i] = c[1][i];
    inArbore[1] = true;
    int total = 0;
    for (int pas = 1; pas < n; pas++)
    {
        int mn = INF, x = 0;
        for (int i = 1; i <= n; i++)                // nodul din afară cel mai aproape de arbore
            if (!inArbore[i] && d[i] < mn) { mn = d[i]; x = i; }
        inArbore[x] = true;
        total += mn;
        for (int y = 1; y <= n; y++)
            if (!inArbore[y] && c[x][y] < d[y]) d[y] = c[x][y];
    }
    cout << total;
    return 0;
}

De ce așa?

Diferența față de Dijkstra. Dijkstra compară d[x] + c[x][y] (costul întregului drum de la sursă); Prim compară doar c[x][y] (costul muchiei care leagă y de arbore). Aceeași structură, alt criteriu.

Dijkstra Roy-Floyd Prim Kruskal
Răspunde la drum minim dintr-un nod drum minim între toate perechile APM APM
Complexitate O(n²) O(n³) O(n²) O(m log m + …)
Costuri negative nu da (fără cicluri negative) da da
Graf orientat sau nu orientat sau nu neorientat conex neorientat
Bun pentru graf mare, o sursă n mic, multe întrebări graf dens graf rar

5. Greșeli frecvente

Greșeala Efect Corect
c[i][j] = 0 pentru „fără muchie” algoritmii folosesc muchii inexistente INF
Floyd cu k în buclă interioară rezultate greșite k este cel mai exterior
uitat < INF la adunare depășire / drumuri false testează c[i][k] < INF && c[k][j] < INF
Dijkstra pe costuri negative distanțe greșite Bellman-Ford sau Floyd
Kruskal fără sortare nu este minim sortezi după cost
int pentru totaluri mari depășire long long

6. La BAC

La BAC

Subiectul cu grafuri cu costuri apare rar la BAC (în special arbori parțiali: „câte muchii trebuie eliminate ca să rămână un arbore” → m − (n − 1), dacă graful este conex). Dijkstra, Floyd, Prim, Kruskal sunt pentru olimpiadă și pentru întrebările de ordine din probleme de algoritmică.

7. Exersează pe hârtie

1. Aplică Dijkstra din nodul 4 pe graful din lecție. Scrie vectorul d după fiecare pas.

2. Ce distanță minimă este între 1 și 5 pe graful din lecție? Care este drumul?

3. Un graf conex are 8 noduri și 15 muchii. Câte muchii trebuie eliminate ca să obții un arbore parțial?

4. Aplică Kruskal pe un graf cu muchiile: A–B 4, A–C 1, B–C 2, B–D 5, C–D 8, C–E 10, D–E 2. Care este costul APM?

5. Costurile sunt negative: A→B 2, A→C 5, C→B −4. Ce distanță A→B calculează Dijkstra? Care este cea corectă?

6. Pe graful orientat 1→2 (4), 2→3 (1), 1→3 (7), 3→1 (2): scrie matricea costurilor, apoi matricea Roy-Floyd.

7. De ce Prim și Kruskal pot da arbori diferiți, dar cu același cost?

8. Câte muchii are un APM al unui graf cu n noduri și p componente conexe (pădure parțială)?

9. Pentru un graf cu 1000 de noduri și 3000 de muchii, ce algoritm alegi pentru drumuri minime din nodul 1: Dijkstra O(n²) sau Floyd O(n³)? Ce număr aproximativ de operații fac?

10. (olimpiadă) Cum modifici Dijkstra ca să numeri câte drumuri minime există din 1 la fiecare nod?

8. Mai departe (pentru cine vrea mai mult)

Dijkstra cu priority_queue, O(m log n). Pui în coadă perechi (distanță, nod) și scoți mereu cea mai mică; folosit pe grafuri cu zeci de mii de noduri.

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, s}); d[s] = 0;
while (!pq.empty())
{
    auto [dist, x] = pq.top(); pq.pop();
    if (dist > d[x]) continue;                   // intrare veche
    for (auto [y, cost] : g[x])
        if (d[x] + cost < d[y]) { d[y] = d[x] + cost; pq.push({d[y], y}); }
}

Bellman-Ford. Acceptă costuri negative, O(n · m): relaxează toate muchiile de n − 1 ori; la a n-a rundă detectează cicluri negative.

DSU (union-find). Structură pentru „sunt x și y în aceeași componentă?”, aproape O(1) cu compresia căilor: face Kruskal O(m log m).

Probleme de olimpiadă. Drum minim cu muchii „gratuite” (CSES Flight Discount), APM cu muchii obligatorii, al doilea cel mai bun arbore.

Rezumat

  • Matricea costurilor: INF = fără muchie, 0 pe diagonală.
  • Dijkstra: fixezi nodul nefixat cu d minim, îmbunătățești vecinii; fără costuri negative; O(n²).
  • Roy-Floyd: k exterior, toate perechile, O(n³).
  • APM: n − 1 muchii; Kruskal (sortare + fără cicluri) sau Prim (arbore care crește).
  • Eliminarea muchiilor pentru a obține arbore: m − (n − 1).

Fișa de lucru

Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.

Fișă de lucru · 5 pagini · 110 min

Grafuri cu costuri

  • Urmărești pas cu pas Dijkstra, Roy-Floyd, Prim și Kruskal și scrii starea vectorilor după fiecare pas.
  • Recunoști greșelile clasice: 0 în loc de INF, k în bucla interioară, criteriul lui Dijkstra pus în Prim.
  • Alegi algoritmul potrivit și îl adaptezi: drum cu escală, centru, muchii deja construite, taxe pe noduri.

Te-ai blocat la un exercițiu?

Probleme de lucru

Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.

  • roy-floyd#589

    ușoară
  • dijkstra#588

    ușoară

Temă

Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.

  • prim#590

    ușoară
  • kruskal#592

    ușoară
  • graf#1651

    ușoară
  • rf#1652

    ușoară
  • firma#591

    medie

Grile din subiectele de BAC

Exerciții de tip grilă din variantele de Bacalaureat. Se rezolvă pe pbinfo.ro, care îți verifică imediat răspunsul.

Citește și exersează în plus

Te-ai blocat la lecția asta?

Scrie-mi ce nu iese și vedem împreună de unde se blochează.

Răspunsuri

Exersează pe hârtie

1. Din 4: d = (∞, ∞, ∞, 0, ∞, ∞). Fixez 4: d[2] = 15, d[3] = 11, d[5] = 6. Fixez 5 (6): d[6] = 6 + 9 = 15. Fixez 3 (11): d[1] = 20, d[2] = min(15, 21) = 15, d[6] = min(15, 13) = 13. Fixez 6 (13): d[1] = min(20, 27) = 20. Fixez 2 (15), apoi 1 (20). Rezultat final: d = (20, 15, 11, 0, 6, 13).

2. 20. Drumul 1 → 3 → 6 → 5 (9 + 2 + 9 = 20). Alt drum, 1 → 3 → 4 → 5, costă 9 + 11 + 6 = 26.

3. 15 − (8 − 1) = 8 muchii.

4. Sortate: A–C 1, B–C 2, D–E 2, A–B 4 (ciclu, respinsă), B–D 5 (leagă {A,B,C} cu {D,E}: ia), ... Muchiile alese: A–C 1, B–C 2, D–E 2, B–D 5 → costul 10.

5. Dijkstra fixează B cu 2 (înainte de C), deci spune 2. Corect: A → C → B = 5 − 4 = 1.

6. Matricea costurilor: (0, 4, 7 / ∞, 0, 1 / 2, ∞, 0). După Floyd: (0, 4, 5 / 3, 0, 1 / 2, 6, 0). De exemplu 1→3: prin 2: 4 + 1 = 5 < 7; 2→1: prin 3: 1 + 2 = 3; 3→2: prin 1: 2 + 4 = 6.

7. Când mai multe muchii au același cost, există mai multe alegeri la fel de bune; arborii diferă, dar costul minim este unic.

8. Pe fiecare componentă are n_i − 1 muchii, în total n − p muchii.

9. Dijkstra: ~ n² = 10⁶ operații; Floyd: n³ = 10⁹ (prea mult pentru o secundă). Alegi Dijkstra (sau varianta cu priority_queue, ~ 3000 · log 1000 ≈ 30 000 operații).

10. Păstrezi nr[x] = numărul de drumuri minime până la x. La îmbunătățire strictă (d[x] + c < d[y]): nr[y] = nr[x]; la egalitate (d[x] + c == d[y]): nr[y] += nr[x].