Grafuri orientate

Proiect realizat de Caramizoiu VladColegiul National Ecaterina Teodoriu

Aplicatii ale grafurilor in viata reala Sa presupunem ca esti in Targu-Jiu,este ora 7:45 si vrei sa ajung la

scoala inainte de ora de incepere a cursurilor ,aceasta fiind situata in partea opusa a orasului .Mai ai la dispozitie 15 minute astfel ca singura ta sansa este sa gaseasci drumul cel mai scurt.

Intr-un moment de sclipire acesta iti dai seama ca reteaua stadala a orasului seaman cu un graf orientat si ca poti ulitiza un program C++ pentru a determina drumul minim.

Inainte de o continua povestea sa ne amintim cate ceva despre grafuri.

Grafuri Orientate– •

• •

•

Asadar trebuia sa realizezi un algoritm care sa calculeze drumul cel mai scurt de la tine de acasa pana la scoala la care inveti.(Daca nu stii realizezi un astfel de algoritm este probabil din cauza ca te jucai asphalt 8 in timp ce profesoara explica grafurile)

Sa presupunem ca fiecare starda(muchie) in functie de

lungimiea sa are un anumit cost.Un astfel de program consta in gasirea lantului de cost minim ce uneste cele 2 puncte .

Un graf caruia i s-a asociat o functie cost se numeste graf

ponderat.Functia cost asociata unai graf se foloseste pentru determinarea drumurilor de cost minim existente intre cele 2 noduri ale graficului.Pentru aceasta fiecarui graf i se asociaza o matrice numita matricea costurilor.Matricea costurilor are 2 variante in functie de scopul in care a fost definita.

Pentru determinarea drumurilor de cost minim se defineste matrice astfel: -M(i,j)=0,daca i=j; - M(i,j)=c(cost),daca i!=j si exista arc de la i la j ; -M(i,j)=∞,daca i!=j si nu exista arc de i la j. Pentru determinarea costului minim intre 2 noduri (x si

y)se pleaca de la matricea initiala M si se transforma aceasta asemanator algoritmului de obtinere al matricei drumurilor alegand fiecare nod ca fiind nod intermediar intre alte 2 noduri

Matricea drumurilor de cost minim se obtine cu algoritmul Roy-Floyd:

#include<fstream.h> ifstream f(“date.in”); ofstream g(“date.out”); int main() {f>>n>>m; for(i=1;i<=n;i++) for(f=1;j<=n;j++) if(i==j) a[i][j]=0; else a[i][j]=9999999;

for(i=1;i<=n;i++) {f>>x>>y>>c; a[x][y]=c;} for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(a[i][j]>a[i][k]+a[k][j]) a[i][j]=a[i][k]+a[k][j]; for(i=1;i<=n;i++){ for(j=1;j<=n;j++) g<< a[i][j]<<’ ‘; g<<’n’;}}

In final probabil nu vei reusii sa faci un program functional ,vei intarzia la scoala ajungand astfel la 10 absente si drept urmare media ta la purtare va avea de suferit de suferit.

Morala: Fii atent la ora de informatica ,nu stii niciodata

cand o sa iti trebuiasca in viata.