Rus Bianca Damaris

grupa 216

Laborator 2

1. Enuntului problemei

Sa se conceapa un algoritm care sa determine drumul de valoare minima de la varful p la varful q , intr-un graf orientat in care se cunosc valorile arcelor(p si q date , oarecare ) , folosind algoritmul lui Bellman Kalaba.

Datele de intrare se dau de la tastatura .

Datele de iesire care prezinta drumul de valoare minima de la varful p la varful q se vor afisa pe ecran .2. Dezvoltarea algoritmului

Algoritmul presupune doi pasi :

a. Citirea matricei costurilor (valorilor arcelor)

b.Modificarea acesteia la calcularea valorilor drumurilor minime

dintre varfuri.

3. Descrierea algoritmului

Algoritmul realizeaza generarea matricii drumurilor optime

dintre oricare 2 varfuri date .

k:=1;

i(k):=lij; Repeta :

Pentru j X executa

i(k+1) =min{ j (k) + li j/ i X sau i -j }

SfPentru

k:=k+1

Panacand (i(k) =i(k-1) ) sau ( k > max{m,n})4. Demonstrarea corectitudinii algoritmului

Tot ceea ce am folosit se gaseste in manual si ni s-a predat la curs 5. Cod sursadef citire_matrice(V,n):

"""

Citeste elementele matricii de valoarea a arcelor.

"""

i = 0

print("Introduceti elementele matricii:")

while i