Algoritmul Roy Floyd

Aspecte teoretice:

Algoritmul Roy Floyd determină costul minim al drumului dintre oricare două vârfuri x,y, precum și un astfel de drum.

Inițial se pornește de la matricea costurilor C, care va fi transformată în matricea drumurilor de cost minim astfel: se consideră un vârf k (k=1,n) și pentru fiecare k se compară costul drumului, din acel moment dintre i și j (i,j=1,n), cu suma costurilor dintre drumul (i,k) și drumul (k,j); în cazul în care costul drumului (i,j) ce trece prin k este mai mic decât drumul existent deja înseamnă că am găsit un nou drum de cost mai mic între vârfurile i și j va fi suma costurilor drumului de la i la k cu drumul de la k la j, iar tata[i][j] va fi tata[k][j] (se va reactualiza vectorul tata pentru a putea reconstitui drumul minim). După finalizarea algoritmului, costul minim al drumului (i,j) este reținut în C[i][j].

Implementare:

Cod Sursa C++

// RoyFloydCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include<iostream>
#include<conio.h>
 
using namespace std;
 
const int pinf=1000;  //pentru plus infinit
int a[20][20],n,m;
 
void citire_cost()
{
	int i,j,x,y,c;
	cout<<"n="; cin>>n;
	cout<<"m="; cin>>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++)
	{
		cout<<"x="; cin>>x;
		cout<<"y="; cin>>y;
		cout<<"c="; cin>>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()
{
	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);
	system("Pause");
}
 
 

Rezultat: