ag_lab2
DESCRIPTION
algoritmica grafelorTRANSCRIPT
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