Proiect - Algoritmul lui Bellman-Kalaba

Algoritmul lui Bellman-Kalaba

1. Determinarea drumului de lungime minima într-un graf

Sa atasam grafului G=(X, U) o matrice , a carei elemente sunt:

Dorim a determina un drum astfel ca:

sa fie minima.

Aceasta revine la a rezolva sistemul de ecuatii

unde în final va reprezenta lungimea drumului minim de la vârful la vârful .

În prima etapa vom considera:

În etapa a doua vom considera:

În etapele urmatoare:

Algoritmul se opreste când avem . În acest caz lungimea drumului de la la va fi data de Afirmatiile de mai sus se bazeaza pe teorema:

Teorema: Daca exista un numar natural k, astkel ca: atunci avem si

Demonstratie: În ipoteza din enunt vom arata prin inductie ca lungimea drumurilor de la la nu poate fi micsorata oricare ar fi numarul de arce componente, adica Conform ipotezei rezulta ca este adevarata pentru . Sa calculam acum Vom avea:

relatie care este adevarata Tinând seama de faptul ca rezulta ceea ce arata ca relatia fiind adevarata pentru , este adevarata pentru orice

Sintetizând cele de mai sus punem în evidenta etapele algoritmului:

a) Se considera matricea de elemente atasata grafului.

b) Se ataseaza coloane suplimentare de elemente care se determina dupa (6). Prima coloana care se ataseaza este identica cu ultima coloana a matricei . Practic fiecare element al unei coloane suplimentare se obtine adunând coloana precedenta, element cu element cu fiecare linie a lui si retinând valoarea minima.

Algoritmul ia sfârsit când se obtin doua coloane identice. Primul element de pe ultima coloana va reprezenta lungimea drumului minim de la la

Succesiunea vârfurilor în graf este data de relatiile: