Algoritmi de optimizare in grafuri
Algoritmi de optimizare in grafuri
Fragment:
" Teorema 2.3. Algoritmul Bellman-Ford determina distantele d(s,y) si drumurile minime D syp, yE V, in raport cu varful sursa s din graful orientat G=(V,A) cu functia valoare v:A--> R.
Demonstratie. Pentru inceput aratam ca la al i -lea pas din ciclul repeta avem urmatorul rezultat: daca d(x)#infinit, atunci reprezinta valoarea unui drum de la s la x. Aratam prin inductie dupa numarul de iteratii a ciclului repeta . La iteratia 0 avem pasul 1 al algoritmului, care este evident. Fie iteratia i, consideram momentul cand distanta la un varf x d(x) este actualizata cu d(y)+v(y,x). Din ipoteza inductiei d(y) este valoarea unui drum de la s la y. Atunci d(y)+ valoarea arcului (y,x) este valoarea unui drum de la s la x care trece prin y.
Deoarece un drum de la varful s la oricare alt varf poate sa contina cel mult n-1 arce, rezulta ca, atunci cand nu exista circuite cu valoare negativa, corpul ciclului repeta se poate executa de cel mult n ori. Daca corpul ciclului repeat se executa si a n+1 oara atunci graful contine circuite cu valoare negativa.
Cand s-a ajuns la pasul 3 algoritmul determina drumurile minime de la varful sursa s catre toate celelalte varfuri, daca Presupunem ca d(x) nu reprezinta drumul minim de la s la x. Asta inseamna ca exista un arc (y,x) cu proprietatea ca d(y)+v(y,x)<d(x). Dar asta contrazice faptul ca iesirea din ciclul repeta se face cand, dupa o parcurgere a tuturor arcelor sirul d nu a suferit nici o modificare (adica nici o valoare d(x) nu mai poate fi micsorata). "
Descrierea produsului
Fragment:
" Teorema 2.3. Algoritmul Bellman-Ford determina distantele d(s,y) si drumurile minime D syp, yE V, in raport cu varful sursa s din graful orientat G=(V,A) cu functia valoare v:A--> R.
Demonstratie. Pentru inceput aratam ca la al i -lea pas din ciclul repeta avem urmatorul rezultat: daca d(x)#infinit, atunci reprezinta valoarea unui drum de la s la x. Aratam prin inductie dupa numarul de iteratii a ciclului repeta . La iteratia 0 avem pasul 1 al algoritmului, care este evident. Fie iteratia i, consideram momentul cand distanta la un varf x d(x) este actualizata cu d(y)+v(y,x). Din ipoteza inductiei d(y) este valoarea unui drum de la s la y. Atunci d(y)+ valoarea arcului (y,x) este valoarea unui drum de la s la x care trece prin y.
Deoarece un drum de la varful s la oricare alt varf poate sa contina cel mult n-1 arce, rezulta ca, atunci cand nu exista circuite cu valoare negativa, corpul ciclului repeta se poate executa de cel mult n ori. Daca corpul ciclului repeat se executa si a n+1 oara atunci graful contine circuite cu valoare negativa.
Cand s-a ajuns la pasul 3 algoritmul determina drumurile minime de la varful sursa s catre toate celelalte varfuri, daca Presupunem ca d(x) nu reprezinta drumul minim de la s la x. Asta inseamna ca exista un arc (y,x) cu proprietatea ca d(y)+v(y,x)<d(x). Dar asta contrazice faptul ca iesirea din ciclul repeta se face cand, dupa o parcurgere a tuturor arcelor sirul d nu a suferit nici o modificare (adica nici o valoare d(x) nu mai poate fi micsorata). "
Detaliile produsului