Drumuri optime în grafuri

Într-un graf orientat ponderat, fiecare arc are o valoare, precum distanța sau costul. Costul unui drum este suma ponderilor arcelor sale. Drumul optim între două vârfuri este cel cu costul cel mai mic dintre drumurile admise.

Exemplu rezolvat. Avem arcele $A\to B$ de cost $4$, $B\to C$ de cost $3$ și $A\to C$ de cost $10$, unde numerele sunt costuri.

1. Drumul direct $A-C$ costă $10$.
2. Drumul $A-B-C$ costă $4+3=7$.
3. Dintre aceste drumuri, cel prin $B$ este mai ieftin, cu cost $7$.

Pentru ponderi nenegative, algoritmul lui Dijkstra pornește cu distanța $0$ în sursă și $\infty$ în celelalte vârfuri. La fiecare pas fixează vârful accesibil cu cel mai mic cost provizoriu și actualizează costurile vârfurilor în care intră arcele ce pleacă din el. Costul unui drum este suma ponderilor arcelor sale. Dacă există arce cu pondere negativă, justificarea algoritmului nu mai este valabilă în general.

Exemplu rezolvat. Luăm arcele $(A,B)$ de cost $9$, $(A,C)$ de cost $2$, $(C,B)$ de cost $3$, $(C,D)$ de cost $8$ și $(B,D)$ de cost $1$. Pornim din $A$. După fixarea lui $A$, costurile sunt $d(B)=9$, $d(C)=2$, $d(D)=\infty$. Fixăm apoi $C$: costul lui $B$ scade la $2+3=5$, iar al lui $D$ la $2+8=10$. Fixăm $B$: costul lui $D$ scade la $5+1=6$.

Predecesorii refac drumul optim $A\to C\to B\to D$, cu costul $2+3+1=6$. Drumul direct $A\to C\to D$ costă $10$.

Într-un graf neponderat, drumul optim este cel cu număr minim de arce, găsit prin parcurgere pe niveluri: întâi vârfurile aflate la distanța $1$ de sursă, apoi cele la distanța $2$ și așa mai departe. În grafurile ponderate, numărul de arce și costul nu sunt același lucru; un drum cu mai multe arce poate avea cost mai mic. Algoritmul lui Dijkstra se oprește când toate vârfurile accesibile au fost fixate; un vârf rămas cu costul $\infty$ nu poate fi atins din sursă. Pentru reconstrucția drumului, la fiecare vârf se reține predecesorul care a produs ultima îmbunătățire a costului.

Exemplu rezolvat. Graful orientat are arcele $S\to A$ de cost $7$, $S\to B$ de cost $2$, $B\to A$ de cost $3$, $A\to T$ de cost $1$ și $B\to T$ de cost $8$. Află drumul optim de la $S$ la $T$.

1. Pornim cu $d(S)=0$ și fixăm $S$: $d(A)=7$, $d(B)=2$, $d(T)=\infty$.
2. Cel mai mic cost provizoriu este $d(B)=2$; fixăm $B$: pentru $A$ avem $2+3=5<7$, deci $d(A)=5$; pentru $T$ avem $2+8=10$.
3. Fixăm $A$ (cost $5$): $d(T)=5+1=6<10$.
4. Predecesorii dau drumul $S\to B\to A\to T$ de cost $2+3+1=6$.

Drumul direct $S\to A\to T$ costă $7+1=8$, iar $S\to B\to T$ costă $10$, deci ambele sunt mai scumpe.

Exemplu rezolvat. Un drum între două orașe trece prin $3$ arce de cost $4$ fiecare, iar altul printr-un singur arc de cost $15$. Care este optim?

1. Primul drum costă $3\cdot 4=12$.
2. Al doilea costă $15$.
3. Optim după cost este primul drum, deși are mai multe arce.

Caz-limită: pondere negativă. Arcele sunt $S\to A$ de cost $2$, $S\to B$ de cost $3$ și $B\to A$ de cost $-2$. Dijkstra fixează $A$ cu $d(A)=2$, apoi nu mai revine asupra lui, deși drumul $S\to B\to A$ costă $3-2=1$.

Greșeli frecvente

• Greșit: drumul cu cele mai puține arce este mereu cel cu costul minim.
  Corect: în exemplul de mai sus, drumul cu $3$ arce costă $12$, mai puțin decât drumul cu $1$ arc, de cost $15$.
• Greșit: în tabelul din exemplu se fixează $B$ cu distanța $9$ imediat după $A$.
  Corect: se fixează mai întâi $C$, cu distanța $2$; arcul $(C,B)$ reduce apoi distanța lui $B$ la $5$.
• Greșit: se aplică Dijkstra fără verificarea ponderilor.
  Corect: metoda standard cere ponderi nenegative.
• Greșit: din $A\to B$ de cost $9$ și $A\to C\to B$ de cost $2+3$ se alege primul drum fiindcă are un singur arc.
  Corect: costurile sunt $9$ și $5$, deci al doilea drum este mai ieftin.

Înainte și după