ag_lab2
-
Upload
bianca-damaris-nicola -
Category
Documents
-
view
3 -
download
0
description
Transcript of ag_lab2
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