Algoritmul lui Dijkstra

Noțiuni preliminare

Graful ponderat este graful în care fiecărei muchii sau fiecărui arc i se asociază o valoare numerică, numită cost sau pondere. Costul poate reprezenta o distanță, o durată, un preț sau orice altă mărime care se acumulează de-a lungul parcurgerii. Pentru un graf orientat cu n vârfuri, costurile se rețin de obicei în matricea costurilor, în care elementul de pe linia i și coloana j este costul arcului de la i la j, valoarea 0 pe diagonala principală și o valoare convențională, mai mare decât orice cost posibil, acolo unde arcul lipsește.

Drumul de la vârful x la vârful y este o succesiune de vârfuri, începând cu x și terminându-se cu y, în care oricare două vârfuri consecutive sunt legate printr-un arc, parcurs în sensul lui.

Costul unui drum este suma costurilor arcelor care îl compun. Un drum de cost minim de la x la y este drumul pentru care această sumă are valoarea cea mai mică dintre toate drumurile de la x la y. Între două vârfuri pot exista mai multe drumuri de cost minim, iar între unele perechi de vârfuri poate să nu existe niciun drum.

Descrierea algoritmului în limbaj natural

Algoritmul lui Dijkstra determină costurile minime ale drumurilor de la un vârf de plecare, notat x, la toate celelalte vârfuri ale grafului. Algoritmul se aplică numai grafurilor cu costuri pozitive.

Se folosesc două structuri: un vector d, în care d[i] reține costul minim cunoscut până în acel moment pentru drumul de la x la i, și o mulțime S a vârfurilor pentru care costul minim a fost stabilit definitiv.

Inițializarea. Mulțimea S conține numai vârful x, iar d[x] este 0. Pentru fiecare alt vârf i, d[i] primește costul arcului direct de la x la i, dacă acesta există, sau valoarea convențională care marchează absența drumului.

Pasul care se repetă. Dintre vârfurile care nu se află încă în S se alege vârful u cu valoarea d[u] cea mai mică. Acest vârf se adaugă la S, iar valoarea d[u] devine definitivă. Apoi, pentru fiecare vârf v rămas în afara lui S, se verifică dacă drumul care trece prin u are un cost mai mic decât cel cunoscut până atunci: dacă d[u] plus costul arcului de la u la v este mai mic decât d[v], atunci d[v] primește această valoare mai mică. Operația se numește relaxare.

Oprirea. Pasul se reia până când toate vârfurile au intrat în S sau până când vârfurile rămase au toate valoarea convențională, semn că la ele nu se poate ajunge din x. Pentru un graf cu n vârfuri se fac cel mult n−1 astfel de pași.

Algoritmul se bazează pe următoarea proprietate: vârful cu cea mai mică valoare d dintre cele rămase nu mai poate fi atins pe alt drum cu un cost mai mic, fiindcă orice alt drum spre el ar trece printr-un vârf din afara lui S, deci ar avea deja un cost cel puțin egal. Raționamentul nu mai este valabil dacă în graf există costuri negative, de aceea algoritmul se aplică numai grafurilor cu costuri pozitive.

Exemplificarea etapelor

Se ia graful orientat ponderat cu 7 vârfuri de mai jos, iar vârful de plecare este 1.

Se notează cu ∞ valoarea convențională pentru vârfurile la care încă nu s-a găsit drum.

Ce se întâmplă la fiecare pas:

• Inițializare. S = {1}. Vârfurile 2, 3 și 6 primesc costurile arcelor directe: 7, 9 și 14.
• Pasul 1. Se alege vârful 2, cu cel mai mic cost, 7. Prin el se ajunge la 3 cu 7 + 10 = 17, mai mult decât 9, deci d[3] nu se schimbă; la 4 se ajunge cu 7 + 15 = 22, prima valoare finită.
• Pasul 2. Se alege vârful 3, cu costul 9. Prin el, drumul spre 4 costă 9 + 11 = 20, mai puțin decât 22, iar drumul spre 6 costă 9 + 2 = 11, mai puțin decât 14. Amândouă valorile se îmbunătățesc. Aici se vede de ce arcul direct 1→6, de cost 14, nu dă drumul de cost minim.
• Pasul 3. Se alege vârful 6, cu costul 11, iar prin el vârful 5 primește 11 + 9 = 20.
• Pasul 4. Vârfurile 4 și 5 au amândouă costul 20. Se alege oricare dintre ele, aici vârful 4; rezultatul final nu se schimbă. Prin 4 se ajunge la 5 cu 20 + 6 = 26, mai mult decât 20, deci d[5] rămâne; la 7 se ajunge cu 20 + 12 = 32.
• Pasul 5. Se alege vârful 5, cu costul 20, iar prin el drumul spre 7 costă 20 + 4 = 24, mai puțin decât 32.
• Pasul 6. Se alege vârful 7, cu costul 24. Nu mai are arce care ies din el, iar toate vârfurile au intrat în S, deci algoritmul se oprește.

Costurile minime de la vârful 1 sunt: 0, 7, 9, 20, 20, 11 și 24. Drumul de cost minim de la 1 la 7 este 1 → 3 → 6 → 5 → 7, cu costul 9 + 2 + 9 + 4 = 24, deși la pasul 4 valoarea d[7] fusese stabilită provizoriu la 32, prin arcul 4→7.

Problema propusă

Enunț. Rețeaua de străzi a unui oraș are n intersecții, numerotate de la 1 la n, legate prin m tronsoane cu sens unic. Pentru fiecare tronson se cunosc intersecția de plecare, intersecția de sosire și timpul de parcurgere, în minute. Serviciul de ambulanță se află în intersecția x. Se cere să se determine, pentru fiecare intersecție, timpul minim în care ambulanța poate ajunge la ea, iar pentru intersecțiile la care nu se poate ajunge să se afișeze valoarea −1.

Datele se citesc din fișierul dijkstra.in, care conține pe prima linie valorile n, m și x, iar pe fiecare dintre următoarele m linii câte trei numere: cele două intersecții și timpul de parcurgere. Se știe că 1 ≤ n ≤ 50, iar timpul de parcurgere al fiecărui tronson este un număr natural cel mult egal cu 1000.

Descrierea soluției în limbaj natural. Rețeaua de străzi se modelează printr-un graf orientat ponderat: intersecțiile sunt vârfurile, tronsoanele cu sens unic sunt arcele, iar timpii de parcurgere sunt costurile. Timpul minim de deplasare din intersecția x la o altă intersecție este costul drumului de cost minim de la vârful x la vârful corespunzător, deci problema se rezolvă cu algoritmul lui Dijkstra, aplicat o singură dată, cu plecare din x.

Costurile se rețin în matricea costurilor, inițializată cu 0 pe diagonala principală și cu o valoare convențională mare în rest, peste care se scriu costurile citite din fișier. Se inițializează vectorul d cu linia x a matricei și mulțimea S cu vârful x.

Se repetă apoi, de n−1 ori, alegerea vârfului neselectat cu cel mai mic cost, adăugarea lui la S și relaxarea tuturor vârfurilor rămase. Dacă la un pas toate vârfurile din afara lui S au încă valoarea convențională, înseamnă că la ele nu se poate ajunge din x, iar repetarea se oprește, deoarece valorile rămase nu mai pot fi modificate.

La afișare, pentru vârfurile cu valoarea convențională se scrie −1.

Implementarea soluției.

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

const int INF = 1000000;   // mai mare decat orice cost real posibil

int c[51][51];   // matricea costurilor
int d[51];       // costul minim cunoscut, de la x la fiecare varf
bool S[51];      // varfurile cu cost stabilit definitiv
int n, m, x;

int main() {
    ifstream f("dijkstra.in");
    f >> n >> m >> x;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            c[i][j] = (i == j) ? 0 : INF;

    for (int k = 1; k <= m; k++) {
        int i, j, cost;
        f >> i >> j >> cost;
        c[i][j] = cost;      // arc cu sens unic, deci nu si c[j][i]
    }
    f.close();

    for (int i = 1; i <= n; i++) {
        d[i] = c[x][i];
        S[i] = false;
    }
    d[x] = 0;
    S[x] = true;

    for (int pas = 1; pas < n; pas++) {
        /* Varful neselectat cu cel mai mic cost. */
        int u = 0, minim = INF;
        for (int i = 1; i <= n; i++)
            if (!S[i] && d[i] < minim) {
                minim = d[i];
                u = i;
            }

        /* Nu mai exista niciun varf accesibil: restul raman neatinse. */
        if (u == 0)
            break;

        S[u] = true;

        /* Relaxarea: drumul prin u are cost mai mic? */
        for (int v = 1; v <= n; v++)
            if (!S[v] && d[u] + c[u][v] < d[v])
                d[v] = d[u] + c[u][v];
    }

    for (int i = 1; i <= n; i++)
        if (d[i] == INF)
            cout << -1 << " ";
        else
            cout << d[i] << " ";

    return 0;
}

Verificarea pe graful din exemplificare. Pentru fișierul care conține 7 11 1 pe prima linie și cele unsprezece arce pe liniile următoare, programul afișează 0 7 9 20 20 11 24 — exact valorile obținute în tabelul de mai sus.