Drumuri minime si drumuri maxime

intr-un graf

Consideram un graf orientat G=(V,U) cu n

varfuri,in care fiecarui arc, ii asociem un cost (nr. intreg) , semnificatia acestui cost poate fi de exemplu: costul deplasarii unui autoturism..;

Matricea costurilor este o matrice A cu n linii si m coloane care poate avea 2 forme:

c, daca exista arc de cost c>0 de la i la

j; A= 0, daca i=j; +∞,daca nu exista arc;

F1

c, daca exista arc de cost de la i

la j; A= 0, daca i=j; -∞, daca nu exista arc de cost

de la i la j;

F2

V={(1,2) (1,4) (2,4) (3,2) (3,4)} u1 u2 u3 u4 u5u1=7; u3=4; u5=2;u2=3; u4=6;

0 7 +∞ 3 A= +∞ 0 +∞ 4 +∞ 6 0 2 +∞ +∞ +∞ 0

1

2

3

4

Un drum este minim atunci

cand lungimea lui este cea mai mica si se numeste drum de cost minim.

Un drum este maxim cand lungimea lui este cea mai mare si se numeste drum de cost maxim.

Exista 3 posibilitati de a determina drumul optim:

-sursa sigura, destinatie unica (intre 2 noduri date);

-sursa unica , destinatie multipla (Dijkstra);

-sursa multipla, destinatie multipla (Roy-Floyd);

V={(1,2)(1,4)(2,3)(3,2)(4,3)(5,1)} u1 u2 u3 u4 u5 u6 u1= 4; u2=6; u3=9;u4=1 ; u5=7; u6=3;

1

2

34

5

0 4 +∞ 6 +∞ +∞ 0 1 +∞ +∞ pentru

drumuri A= +∞ 9 0 7 +∞ minime +∞ +∞ +∞ 0 +∞ 3 +∞ +∞ +∞ 0

0 4 -∞ 6 -∞ pentru drumuri

-∞ 0 1 -∞ -∞ maxime

A= -∞ 9 0 7 -∞ -∞ -∞ -∞ 0 -∞ 3 -∞ -∞ -∞ 0

Algoritmul lui Roy-Floyd# include<iostream.h>float a[50][50];int n; void drum(int i , int j) {int k=1, gasit=0; while ((k<=n) &&(gasit==0)) {if ((i!=k) && (j!=k)) a[i][j]=a[i][k]+a[k][j]; { drum(i,k); drum (k,j); gasit=1;} k++;{ if(gasit==0)cout<< j<<“ ”;} void scrie_drum(int nod_initial, int nod_final) { if (a[nod_initial][nod_final]<pinfint) {cout<<“drumul de la”<<nod_initial<<“la”<<nod_final<<“are

lungimea”<<a[nod_initial][nod_final]<<endl; cout<<nod_initial<<“ ”; drum(nod_initial, nod_final);} elsecout<<“nu exista drum de la”<<nod_initial<<“la”<<nod_final;}

void lungime_drumuri () { int i , j , k; 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];}void citire_cost() { cout<< “ n= “; cin >> n ; for (i=1 ; i<=n; i++ ) for (j=1; j<=n; j++) cin >>a[i][j]; }void main () { citire_cost(); lungime_drumuri(); scriu_drum( 5,p);}

Algoritmul lui Dijkstra# include<iostream.h>float a[50][50] ,d[50], min ;int s[50], t[50], n, i, j, r, poz ; void drum ( int i){ if t[i]==1) drum ( t[i] ); cout<< i<<“ ”; }void main (){ cout<<“dati nr. de noduri ”; cin>> n ; for(i=1; i<=n; i++) for (j=1; j<=n; j++) cin>> a[i] [j] ; } cout<<“ dati nodul de plecare ”; cin>> r ; s[ r]=1; for( i=1; i<=n; i++) {d [ i]= a[ r][ i] ; if ( i != r) if ( d[ i]< pinfinit ) t [ i]= r; } for (i=1; i<=n-1; i++) {min= pinfinit ; for (j=1; j<=n; j++) if ( s[j ]==0) if ( d[ j]<min ) { min = d[ j ] ; poz=j; }

s [poz]=1;for (j=1; j<=n; j++) if (s[ j]==0) if (d [j]> d [poz]+a[poz][ j]) { d [ j]=d[poz]+a[poz][ j] ; t[ j]=poz ; } }for (i=1; i<=n; i++) cout<< d[ i]<<“ ”; cout<<endl; for (i=1; i<=n; i++) if (i != r) if (t[ i]==1) cout<<“distanta de la”<< r<<“la”<<

i<<“este”<< d [ i] <<endl ; drum ( i) ; else cout<<“nu exista drum de la”<< r<<“ la ”<<

i<<endl; }