Grafuri ponderate. Drumuri de cost minim

În multe probleme, fiecărei legături dintre două obiecte îi corespunde o valoare: două localități sunt legate prin șosele de lungimi diferite, un zbor are un preț, o stradă se parcurge într-un anumit timp. Asemenea date se reprezintă printr-un graf ponderat, în care fiecare muchie sau arc are asociat un număr, numit cost. Întrebarea obișnuită pentru un graf ponderat este care este drumul de cost minim între două noduri.

Programa cere doi algoritmi:

• algoritmul Roy-Floyd, care determină costurile minime între toate perechile de noduri;
• algoritmul lui Dijkstra, care determină costurile minime de la un nod dat la toate celelalte noduri.

Noțiuni preliminare

Drumurile de cost minim se definesc cu ajutorul următoarelor noțiuni:

• graful orientat este o pereche G = (X, U), în care X este o mulțime finită și nevidă de noduri, iar U o mulțime de perechi ordonate de noduri distincte, numite arce;
• graful neorientat este o pereche G = (X, U), în care U este o mulțime de perechi neordonate de noduri distincte, numite muchii;
• două noduri x și y sunt adiacente dacă între ele există o muchie sau un arc;
• drumul este, într-un graf orientat, o succesiune de noduri (x1, x2, …, xk) în care pentru oricare două noduri consecutive există arcul (xi, xi+1); la graful neorientat, succesiunea corespunzătoare se numește lanț.

Terminologia completă este în subcapitolul Grafuri orientate și neorientate. Terminologie.

Graful ponderat

Definiție

Un graf ponderat, numit și graf cu costuri, este un graf G = (X, U) împreună cu o funcție cost f : U → R+. Funcția atribuie fiecărei muchii sau fiecărui arc u un număr real pozitiv f(u), numit costul lui u.

Costul poate reprezenta o distanță, un timp de parcurgere, un preț sau orice altă mărime care se adună pe măsură ce se înaintează pe drum.

Costul unui drum este suma costurilor arcelor care îl formează. Un drum de cost minim de la nodul x la nodul y este un drum de la x la y al cărui cost este cel mai mic dintre costurile tuturor drumurilor de la x la y.

Exemplu. Graful orientat ponderat G9 are nodurile {1, 2, 3, 4, 5, 6} și arcele, cu costurile scrise lângă ele:

(1,2) 10   (1,3) 3   (3,2) 4   (2,4) 2   (3,4) 8
(3,5) 2    (5,4) 5   (4,6) 1   (5,6) 7

De la nodul 1 la nodul 6 există mai multe drumuri, cu costuri diferite:

Drumul de cost minim de la 1 la 6 este (1, 3, 2, 4, 6), cu costul 10. El are patru arce, deși există drumuri cu trei arce: drumul de cost minim nu este, în general, drumul cu cele mai puține arce. Drumul cu cele mai puține arce se determină prin parcurgerea în lățime, prezentată în subcapitolul Parcurgerea grafurilor.

Probleme care se rezolvă cu grafuri ponderate

Matricea costurilor

Un graf ponderat se reprezintă de obicei prin matricea costurilor. Pentru un graf cu n noduri, ea este matricea pătratică c, cu n linii și n coloane, în care:

c[i][j] = cost, dacă există arcul (i,j) și are costul cost
c[i][j] = 0, dacă i = j
c[i][j] = ∞, dacă i ≠ j și nu există arcul (i,j)

Matricea costurilor pentru graful G9:

Matricea costurilor are următoarele proprietăți:

• la graful neorientat este simetrică: muchia [i, j] se trece și în c[i][j], și în c[j][i];
• la graful orientat nu este, în general, simetrică;
• valoarea ∞ se alege mare pentru ca un arc inexistent să nu fie ales niciodată la căutarea costului minim.

Într-un program, ∞ se înlocuiește cu o constantă, notată aici infinit, mai mare decât costul oricărui drum posibil. Constanta nu se ia egală cu cea mai mare valoare a tipului întreg: suma c[i][k] + c[k][j] ar depăși domeniul tipului și ar da un rezultat negativ, care ar părea un cost foarte mic. Programele din această lecție folosesc infinit = 1000000000: suma a două asemenea valori, 2000000000, încape încă în tipul int, iar un drum care trece printr-un arc inexistent are un cost mai mare decât infinit și nu este ales niciodată.

Matricea se construiește în doi pași:

1. elementele de pe diagonala principală primesc valoarea 0, iar celelalte valoarea infinit;
2. pentru fiecare arc (i, j) citit, cu costul cost, se face c[i][j] = cost; la graful neorientat se face și c[j][i] = cost.

Pentru determinarea drumurilor de cost maxim se folosește matricea costurilor maxime, în care arcele inexistente primesc o valoare foarte mică (−∞).

Principiul optimalității

Ambii algoritmi se bazează pe principiul optimalității, enunțat de Bellman:

dacă drumul de cost minim de la nodul i la nodul j trece prin nodul k, atunci porțiunea lui de la i la k este un drum de cost minim de la i la k, iar porțiunea de la k la j este un drum de cost minim de la k la j.

Justificare: dacă ar exista un drum mai ieftin de la i la k, el ar înlocui porțiunea respectivă și s-ar obține un drum de la i la j mai ieftin decât cel minim, ceea ce este imposibil.

În G9, drumul minim (1, 3, 2, 4, 6) trece prin nodul 2, iar porțiunea (1, 3, 2), cu costul 7, este chiar drumul minim de la 1 la 2. Deosebirea dintre cei doi algoritmi stă în felul în care aleg nodurile intermediare k.

Algoritmul Roy-Floyd

Descrierea algoritmului

Algoritmul Roy-Floyd transformă matricea costurilor astfel încât, la sfârșit, c[i][j] este costul minim al unui drum de la i la j. Nodurile k = 1, 2, …, n se iau pe rând ca noduri intermediare. Pentru fiecare k și pentru fiecare pereche (i, j), dacă drumul de la i la k continuat cu drumul de la k la j costă mai puțin decât drumul cunoscut de la i la j, costul acestuia se înlocuiește:

c[i][j] ← c[i][k] + c[k][j], dacă c[i][k] + c[k][j] < c[i][j]

După ce s-au folosit ca intermediare nodurile 1, …, k, c[i][j] este costul minim al unui drum de la i la j ale cărui noduri intermediare sunt toate printre nodurile 1, …, k. După k = n sunt permise toate nodurile, deci matricea conține costurile minime. Algoritmul are aceeași structură ca algoritmul Roy-Warshall pentru matricea drumurilor, prezentat în subcapitolul Matricea drumurilor. Conexitate.

royFloyd:
    pentru k ← 1, n execută
        pentru i ← 1, n execută
            pentru j ← 1, n execută
                dacă c[i][k] + c[k][j] < c[i][j]
                atunci
                    c[i][j] ← c[i][k] + c[k][j]
                sfdacă
            sfpentru
        sfpentru
    sfpentru

void royFloyd() {
    for (int k = 1; k <= n; k++)                // nod intermediar
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (c[i][j] > c[i][k] + c[k][j])
                    c[i][j] = c[i][k] + c[k][j];
}

Structura repetitivă după nodul intermediar k este cea exterioară. Un drum care trece printr-un arc inexistent are costul cel puțin infinit, deci nu înlocuiește niciodată un cost cunoscut.

Exemplificarea etapelor

Se aplică algoritmul matricei costurilor grafului G9. La fiecare valoare a lui k, următoarele elemente se modifică:

Matricea obținută:

Matricea se citește pe linii: c[1][6] = 10 este costul minim de la 1 la 6, iar c[4][2] = ∞ arată că de la nodul 4 nu există drum la nodul 2. Matricea conține numai costurile, nu și nodurile drumurilor.

Etapele se pot urmări pas cu pas în simulatorul algoritmului Roy-Floyd.

Reconstituirea drumului

Nodurile drumului de cost minim se obțin din matricea transformată, după același raționament: dacă pentru un nod k, diferit de i și de j, c[i][k] + c[k][j] = c[i][j], înseamnă că nodul k se află pe un drum minim de la i la j. Problema se împarte în două subprobleme de același tip — drumul de la i la k și drumul de la k la j —, care se rezolvă la fel, deci se folosește metoda divide et impera. Dacă nu există un asemenea nod k, drumul minim este chiar arcul (i, j).

Pentru G9, de la 1 la 6: c[1][2] + c[2][6] = 7 + 3 = 10 = c[1][6], deci drumul trece prin 2. De la 1 la 2: c[1][3] + c[3][2] = 3 + 4 = 7, deci trece prin 3; de la 2 la 6: c[2][4] + c[4][6] = 2 + 1 = 3, deci trece prin 4. Drumul este (1, 3, 2, 4, 6).

Enunț. Se citește un graf orientat ponderat cu n noduri și m arce, cu costuri naturale nenule, apoi două noduri x și y. Să se afișeze matricea costurilor minime, iar pentru perechea (x, y) costul minim și nodurile unui drum de cost minim sau un mesaj, dacă drumul nu există.

Date de intrare. Pe prima linie n și m, pe fiecare dintre următoarele m linii extremitățile și costul unui arc, pe ultima linie x și y. Pentru graful G9 și perechea (1, 6):

6 9
1 2 10
1 3 3
3 2 4
2 4 2
3 4 8
3 5 2
5 4 5
4 6 1
5 6 7
1 6

#include <iostream>
using namespace std;

const int MAX = 101;
const int infinit = 1000000000;   // suma a doua valori infinit incape in int
int c[MAX][MAX], n, m;

/* Construieste matricea costurilor: 0 pe diagonala principala,
   costul arcului acolo unde arcul exista, infinit in rest. */
void citire() {
    int i, j, cost;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            c[i][j] = (i == j) ? 0 : infinit;
    for (int k = 1; k <= m; k++) {
        cin >> i >> j >> cost;
        c[i][j] = cost;
    }
}

/* Transforma matricea costurilor: pentru fiecare nod intermediar k,
   drumul de la i la j prin k inlocuieste drumul cunoscut,
   daca este mai ieftin. */
void royFloyd() {
    for (int k = 1; k <= n; k++)                // nod intermediar
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (c[i][j] > c[i][k] + c[k][j])
                    c[i][j] = c[i][k] + c[k][j];
}

void afiseazaMatricea() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (c[i][j] == infinit)
                cout << "- ";
            else
                cout << c[i][j] << " ";
        cout << "\n";
    }
}

/* Afiseaza nodurile drumului minim de la i la j, fara nodul i:
   daca exista un nod k prin care costul minim se descompune,
   drumul se afiseaza pe cele doua bucati (divide et impera). */
void drum(int i, int j) {
    for (int k = 1; k <= n; k++)
        if (k != i && k != j && c[i][k] + c[k][j] == c[i][j]) {
            drum(i, k);
            drum(k, j);
            return;
        }
    cout << " " << j;
}

void afiseazaDrum(int x, int y) {
    if (c[x][y] == infinit)
        cout << "Nu exista drum de la " << x << " la " << y << "\n";
    else {
        cout << "Costul minim de la " << x << " la " << y << ": " << c[x][y] << "\n";
        cout << "Drumul: " << x;
        if (x != y)
            drum(x, y);
        cout << "\n";
    }
}

int main() {
    int x, y;
    citire();
    cin >> x >> y;
    royFloyd();
    afiseazaMatricea();
    afiseazaDrum(x, y);
    return 0;
}

Programul afișează (semnul - ține locul valorii ∞):

0 7 3 9 5 10
- 0 - 2 - 3
- 4 0 6 2 7
- - - 0 - 1
- - - 5 0 6
- - - - - 0
Costul minim de la 1 la 6: 10
Drumul: 1 3 2 4 6

Pentru perechea (4, 2) ultimul rând este Nu exista drum de la 4 la 2.

Descrierea soluției. Subprogramul citire construiește matricea costurilor, royFloyd o transformă, iar drum afișează nodurile drumului de la i la j, fără nodul i: caută un nod intermediar k pentru care costul se descompune și se apelează pentru cele două porțiuni; dacă nu găsește, afișează j. Recursivitatea se oprește, fiindcă, la costuri nenule, fiecare porțiune are un cost strict mai mic decât drumul întreg. Subprogramul afiseazaDrum tratează separat cazul în care drumul nu există.

Complexitatea

Cele trei structuri repetitive imbricate se execută fiecare de n ori, deci algoritmul Roy-Floyd are ordinul de complexitate O(n³). Reconstituirea unui drum cere cel mult O(n²) operații: pentru fiecare nod al drumului se caută un nod intermediar printre cele n noduri.

O aplicație: sediul central

Enunț. O firmă are n puncte de lucru, legate prin m șosele cu dublu sens, de lungimi cunoscute. Firma își stabilește sediul central în punctul de lucru pentru care suma distanțelor minime la toate celelalte puncte este cea mai mică. Să se afișeze punctul ales și suma distanțelor.

Date de intrare. Pentru rețeaua cu 5 puncte de lucru și 7 șosele:

5 7
1 2 4
1 3 2
2 3 1
2 4 5
3 4 8
3 5 10
4 5 2

#include <iostream>
using namespace std;

const int MAX = 101;
const int infinit = 1000000000;   // suma a doua valori infinit incape in int
int c[MAX][MAX], n, m;

/* Soselele sunt in ambele sensuri, deci matricea costurilor
   este simetrica. */
void citire() {
    int i, j, cost;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            c[i][j] = (i == j) ? 0 : infinit;
    for (int k = 1; k <= m; k++) {
        cin >> i >> j >> cost;
        c[i][j] = c[j][i] = cost;
    }
}

void royFloyd() {
    for (int k = 1; k <= n; k++)                // nod intermediar
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (c[i][j] > c[i][k] + c[k][j])
                    c[i][j] = c[i][k] + c[k][j];
}

/* Suma distantelor minime de la punctul i la toate celelalte
   sau infinit, daca la un punct nu se poate ajunge. */
int sumaDistantelor(int i) {
    int suma = 0;
    for (int j = 1; j <= n; j++) {
        if (c[i][j] == infinit)
            return infinit;
        suma += c[i][j];
    }
    return suma;
}

/* Punctul cu suma minima a distantelor; la egalitate, primul. */
int alegeSediul() {
    int sediu = 1;
    for (int i = 2; i <= n; i++)
        if (sumaDistantelor(i) < sumaDistantelor(sediu))
            sediu = i;
    return sediu;
}

int main() {
    citire();
    royFloyd();
    int sediu = alegeSediul();
    if (sumaDistantelor(sediu) == infinit)
        cout << "Reteaua nu leaga toate punctele de lucru\n";
    else
        cout << "Sediul: " << sediu << ", suma distantelor: "
             << sumaDistantelor(sediu) << "\n";
    return 0;
}

Programul afișează Sediul: 2, suma distantelor: 16. După transformare, sumele liniilor matricei sunt 23, 16, 17, 21 și 27, deci punctul 2 are suma minimă.

Descrierea soluției. Șoselele au dublu sens, deci graful este neorientat, iar matricea costurilor se completează simetric. Algoritmul Roy-Floyd dă distanțele minime între toate perechile de puncte. Subprogramul sumaDistantelor adună linia unui punct, iar alegeSediul alege linia cu suma minimă. Timpul este de ordinul O(n³), dat de transformarea matricei.

Algoritmul lui Dijkstra

Descrierea algoritmului

Algoritmul lui Dijkstra determină drumurile de cost minim de la un nod start, numit nod sursă, la toate celelalte noduri. Nodurile se împart în două mulțimi:

• mulțimea S a nodurilor selectate, pentru care costul minim de la start este stabilit definitiv;
• mulțimea nodurilor neselectate, pentru care se cunoaște doar un cost provizoriu.

Se folosesc trei vectori:

• viz[i] = 1 dacă nodul i este selectat, 0 în caz contrar;
• d[i] — costul celui mai ieftin drum de la start la i găsit până la momentul respectiv;
• t[i] — nodul dinaintea lui i pe acest drum (predecesorul lui i), sau 0 dacă nu s-a găsit încă drum.