Algoritmul lui Roy-Floyd

Fie G=(V, E) un graf neorientat, unde V are n elemente (n noduri) si E are m elemente (m muchii) memorat prin matricea ponderilor. Se cere ca pentru doua noduri x,y citite sa se determine lungimea minima a lantului de la x la y.

Astfel:

Initial matricea ponderilor pentru nodurile 1 si 4 va retine 10. Se observa ca lantul 1,2,3,4 determina o suma a costurilor mai mica: 2+3+1=6. Lungime minima a lantului de la 1 la 4 este 6.

Algoritmul:

-se genereaza matricea ponderilor:

Unde pinf reprezinta plus infinit

-se incearca pentru oricare pereche de noduri i,j sa se obtina “drumuri” mai scurte prin noduri intermediare k (kÎ1…n).

Acest lucru se determina comparand “lungimea” lantului a[i,j] cu lungimea lantului care trece prin k si daca:

a[i,j] > a[i,k]+a[k,j] atunci se atribuie: a[i,j] ¬ a[i,k]+a[k,j]

Astfel generarea matricii drumurilor optime se realizeaza cu urmatoarea secventa:

for(int k=1;k<=n;k++)

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

if(a[i][j]>a[i][k]+a[k][j])

a[i][j]=a[i][k]+a[k][j];

Se obtine:

In continuare, dupa determinarea matricii lanturilor optime, pentru doua noduri citite x, y se cere sa se reconstituie un lant optim de la x la y (pot fi mai multe solutii).

Solutie:

-se determina daca exista un lant de la x la y (ar putea sa nu existe un astfel de lant daca graful nu este conex):

cand a[x,y] ¹¥

-se descompune “drumul” de la x la y prin k atunci cand: a[x][y]=a[x][k]+a[k][y];

- pentru un astfel de algoritm se utilizeaza strategia Divide et Impera

Iata o solutie:

#include<fstream.h>

#include<conio.h>

const pinf=1000; //pentru plus infinit

int a[20][20],n,m;

void citire_cost()

{fstream f;

int i,j,x,y,c;

f.open("roy.in",ios::in);

if(f)

cout<<"deschiderea a reusit";

else

cout<<"eroare la deschidere!";

cout<<endl;

f>>n>>m;

//initializare matrice

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(i==j)

a[i][j]=0;

else

a[i][j]=pinf;

for(i=1;i<=m;i++)

{f>>x>>y>>c;

a[x][y]=a[y][x]=c;}

}

void afisare_mat()

{for(int i=1;i<=n;i++)

{for(int j=1;j<=n;j++)

if(a[i][j]==pinf)

cout<<"pinf ";

else

cout<<a[i][j]<<" ";

cout<<endl;}

}

void genarare_matrice_drumuri_optime()

{for(int k=1;k<=n;k++)

for(int i=1;i<=n;i++)

for(int 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 descompun_drum(int i,int j) //realizeaza descompunerea portiunii de la i la j prin k

{int g=0,k=1;

while(k<=n&&!g)

{if(i!=k&&j!=k)

if(a[i][j]==a[i][k]+a[k][j])

{descompun_drum(i,k);

descompun_drum(k,j);

g=1;} //g marcheaza daca se poate realiza descompunerea

k++;

}

if(!g)

cout<<j<<" "; //cand “drumul” nu mai poate fi descompus afisez extremitatea finala

}

void scriu_drum(int nodini,int nodfin) // functia primeste ca parametri cele doua noduri pt care se determina optimul

{if(a[nodini][nodfin]<pinf)

{cout<<"lantul de la "<<nodini<<" la "<<nodfin<<" are lungimea "<<a[nodini][nodfin];

cout<<endl<<"un drum optim este: "<<endl;

cout<<nodini<<" ";

descompun_drum(nodini,nodfin); // apeleaza functia care afiseaza efectiv lantul

}

else

cout<<"nu exista drum de la "<<nodini<<" la "<<nodfin;

}

void main()

{clrscr();int x,y;

citire_cost();

cout<<endl<<"matricea ponderilor "<<endl;

afisare_mat();

genarare_matrice_drumuri_optime();

cout<<endl<<"matricea drumurilor optime "<<endl;

afisare_mat();

cout<<endl<<"Se determina drumul minim intre varfurile x si y "<<endl;

cout<<"x=";

cin>>x;

cout<<"y=";

cin>>y;

scriu_drum(x,y);

getch();

}