Tehnici avansate de programare
În comparație cu algoritmul lui Dijkstra, Bellman-Ford are un timp de execuție mai mare dar este mai versatil deoarece este capabil de a suporta grafuri in care costul este negativ.
Algoritmul Bellman-Ford
Algoritmul Bellman-Ford determină drumurile de cost minim de la un vârf graf la fiecare dintre celelalte vârfuri, identificând eventualele circuite de cost negativ.
Descrierea algoritmului
1. Graful este reprezentat prin matricea costurilor.
2. Costurile drumurilor de cost minim determinate până la un moment dat sunt reţinute în vectorul d.
3. Pentru a reconstitui drumul de cost minim se utilizează vectorul pre, în care reţinem pentru fiecare vârf din graf predecesorul său pe drumul de cost minim de la vârful de start.
Algoritmul are două etape : în prima etapă se parcurg toate arcele grafului şi pentru fiecare arc din graf se verifică dacă optimizează costul drumului de cost minim de la vârful de start la extremitatea sa finală ; această verificare se repetă de n ori. in cea de-a doua etapă se verifică dacă există circuite de cost negativ.
Se repetă de n ori:
Pentru fiecare arc (x, y) din graf:
Dacă d [y] >d [x] +C [x] [y] atunci
{ d[y] =d [x] +C [x] [y] ;
pre [y] =x;
}
Pentru fiecare arc (x, y) din graf
Dacă d[y]>d[x]+C[x] [y] atunci
Scrie „Există circuite de cost negativ". Stop
Implementarea algoritmului
Deoarece funcţiile de iniţializare şi de afişare sunt aceleaşi ca în impiemen-tarea algoritmului. lui Dijkstra, vom prezenta numai funcţia Bellman_Ford(). Această funcţie returnează valoarea o dacă, graful conţine un circuit de cost negativ şi respectiv 1 în caz contrar.
int Bellman_Ford()
{
int i, j, k;
for (i=1; j<=n; i++)
for (j=1; j<=n; j++)
for (k=1; k<=n; k++)
if(C[j][k]!=Inf && d[k]>d[j]+C[j][k])
{d[k]=d[j]+C[j][k];
pre[k]=j;}
for (j=1; j<=n; j++)
for (k=1; k<=n; k++)
if (C[i][k] !=inf && d[k]>d[j]+C[j][k])
return 0;
return 1;
}
Observaţii
Complexitatea algoritmului Bellman-Ford este 0(n3).
Algoritmul lui Dijkstra
Algoritmul lui Dijkstra este o metodă de a stabili drumul de cost minim de la un nod de start la oricare altul dintr-un graf. Numele este dat de Edsger Dijkstra, savantul care l-a descoperit.
Mod de aplicare:
-
Se creează o listă cu distanțe, o listă cu nodul anterior, o listă cu nodurile vizitate și un nod curent.
-
Toate valorile din lista cu distanțe sunt inițializate cu o valoare infinită, cu excepția nodului de start, care este setat cu 0.
-
Toate valorile din lista cu nodurile vizitate sunt setate cu fals.
-
Toate valorile din lista cu nodurile anterioare sunt inițializate cu -1.
-
Nodul de start este setat ca nodul curent.
-
Se marchează ca vizitat nodul curent.
-
Se actualizează distanțele, pe baza nodurilor care pot fi vizitate imediat din nodul curent.
-
Se actualizează nodul curent la nodul nevizitat care poate fi vizitat prin calea cea mai scurtă de la nodul de start.
-
Se repetă (de la punctul 6) până când toate nodurile sunt vizitate.
Strategia algoritmului este aceea de minimizare succesivă a costului drumului minim de la p la orice nod j din graf (d[j]) până la obţinerea costului minim.
Această operaţie se face prin verificarea posibilităţii ca fiecare arc (i,j) să participe la minimizarea distanţei de la p la j. Operaţia se face cu o trecere completă prin toate arcele grafului.
Condiţia ca distanţa de la p la j să poată fi minimizată prin arcul (i,j) este ca d[j]>d[i]+c[i,j]
Notăm cu n numărul de noduri din graf. Algoritmul efectuează n-1 treceri complete prin mulţimea arcelor grafului (orice drum elementar poate fi format din maxim n-1 arce). În final, existenţa unui circuit negativ face ca la o nouă trecere prin mulţimea arcelor să fie în continuare posibilă minimizarea costului unui drum. În acest caz algoritmul evidenţiază prezenţa circuitului de cost negativ ce cuprinde nodul sursă.
