Algoritmul Floyd-Warshall pentru determinarea tuturor drumurilor de cost minim

Avem o problema clasica de grafuri. Se da un graf orientat cu N noduri, memorat prin matricea ponderilor. Determinati pentru orice pereche de noduri x si y lungimea minima a drumului de la nodul x la nodul y, afisandu-se matricea drumurilor minime. Prin lungimea unui drum intelegem suma costurilor arcelor care-l alcatuiesc. Problema se gaseste pe infoarena.

Aceasta problema ar putea fi rezolvata prin algoritmi clasici pentru determinarea unui drum de cost minim intre doua noduri in complexitate O(n^3*logn) – cel mai optim. Totusi, algoritmul Floyd-Warshall (sau chiar Roy-Floyd) rezolva problema prin programare dinamica in complexitate n^3. Consideram toate varfurile intermediare k(k=1,2,…,n) si verificam pentru fiecare pereche de varfuri din graf x,y daca trecand prin k se optimizeaza costul de la x la y; in caz afirmativ, costul drumului de la x la y se modifica. Observam ca dupa pasul k in matricea costurilor, pe pozitia (x,y), se afla costul drumului de cost minim de la x la y care trece numai prin varfuri intermediare din multimea {1,2,….,k}.

Aplicarea algoritmului Floyd-Warshall

#include<cstdio>
using namespace std;
void read(),solve(),show();
int n,a[105][105];
int main()
{
	read();
	solve();
	show();
	return 0;
}
void read()
{
	int j;
	freopen("royfloyd.in","r",stdin);
	freopen("royfloyd.out","w",stdout);
	scanf("%d",&n);
	for(int i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			scanf("%d",&a[i][j]);
}
void solve()
{
	int i,j;
	for(int k = 0; k < n; k++)
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++) //daca putem actualiza
				if(a[i][k] && a[k][j] && i != j && (a[i][j] > a[i][k] + a[k][j] || !a[i][j]))
					a[i][j] = a[i][k] + a[k][j];
}
void show()
{
	int j; //afisam matricea costurilor
	for(int i = 0; i < n; i++,printf("\n"))
		for(j = 0 ; j < n; j++)
			printf("%d ", a[i][j]);
}

Algoritmul are o aplicabilitate in diverse probleme de informatica dar si in alte categorii ale domeniului de programare. Pentru a aprofunda si mai bine algoritmul am ales o problema ceva mai dificila ce se bucura de o solutie folosind algoritmul prezentat anterior.

Problema Coach

Sunteti antrenorul ciclistului Adirem Onamihs care, in ciuda numelui ciudat, este foarte talentat. In curant va avea loc un eveniment sportiv, un prilej foarte bun de a-l antrena pe ciclist. Pentru organizarea evenimentului s-au amenajat N intersectii si M drumuri bidirectionale intre aceste intersectii. Pentru fiecare drum se cunosc numarul de minute necesare pentru parcurgerea lui. La fiecare intersectie ciclistul care trece pe acolo este obligat sa serveasca o bautura energizanta si racoritoare. Bautura difera de la intersectie la intersectie si se cunosc deja numarul de calorii ale fiecarei bauturi.

Ca un mare antrenor, aveti un plan special pentru Adirem. Doriti ca durata traseului pe care il alege Adirem sa aiba exact T ore, insa nu vreti sa-i planuiti intregul traseu (Adirem trebuie sa isi antreneze si mintea, nu numai corpul). Ii veti preciza lui Adirem doar intersectia de unde isi incepe traseul si intersectia unde il termina. Adirem invata repede – el stie intotdeauna sa aleaga traseul optim (drumul cel mai scurt dintre cele doua intersectii). Atunci cum il puteti face sa mearga exact T ore? Dupa cateva portii de creatina, va vine ideea salvatoare: ii veti interzice trecerea prin anumite intersectii, sub pretextul ca valoarea calorica a bauturii servite in intersectia respectiva nu este benefica pentru antrenamentul lui. Astfel, ii veti preciza o limita inferioara si una superioara pentru numarul de calorii ale bauturilor pe care el are voie sa le bea. Adirem nu va trece decat prin intersectiile unde se serveste o bautura cu valoare calorica intre limitele date.

Cum numarul de intersectii este destul de mare, va trebui sa scrieti un program care sa calculeze cele patru variabile in antrenamentul lui Adirem: intersectia de start, intersectia de finish, valoarea calorica minima pe care poate sa o consume si valoarea calorica maxima, astfel incat drumul cel mai scurt dintre cele doua intersectii (care sa respecte restrictiile) sa dureze T minute.

Solutie Coach

Se observa aproape imediat nevoia stabilirii tuturor drumurilor minime. Particularitatea problemei o constituie faptul cum va fi afisata solutia – intre doua valori intermediare (in functie de valorile calorice ale bauturilor). Putem sa ne folosim de proprietatea algoritmului prezentata mai sus si sa deducem ca putem sorta nodurile dupa valoarea fiecaruia avand grija sa renumerotam nodurile. Vom fixa un nod de inceput „start” (si implicit un cost minim), dupa care aplicam algoritmul Floyd-Warshall pentru nodurile cu valoarea cel putin egala cu costul minim (avand grija sa luam doar nodurile de la s la N). Proprietatea pe care ne bazam este urmatoarea : la pasul k (s <= k <= N), avem C[i][j] este drumul minim de la i la j care poate trece prin nodurile cuprinse intre s si k. Implementand aceasta abordare a problemei vom avea complexitatea O(n^4) ce vine din algoritmul Floyd-Warshall + particularitatea noastra de a parcurge toate costurile sortate.

#include<cstdio>
#include<iostream>
#define INF 1<<25
using namespace std;
int n[101],NN[101],RNN[101],ori[101][101],a[101][101],N,M,T,start,end,smax,smin;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	int i,j,c,aux;
	freopen("coach.in","r",stdin);
	freopen("coach.out","w",stdout);
	scanf("%d%d%d",&N,&M,&T);
	for(i=1;i<=N;i++)
		scanf("%d",&n[i]),RNN[i]=NN[i]=i;
	 
	//sortam si renumeratom indicii simultan
	for(i=1;i<N;i++)
		for(j=i+1;j<=N;j++)
			if(n[i] > n[j])
			{
				RNN[NN[i]]=j;RNN[NN[j]]=i;
				aux=n[i];n[i]=n[j];n[j]=aux;
				aux=NN[i];NN[i]=NN[j];NN[j]=aux;
			}
	//citim muchiile renumerotate ca se le asezam unde trebuie
	for(;M;M--)
		scanf("%d%d%d",&i,&j,&c),ori[RNN[j]][RNN[i]]=ori[RNN[i]][RNN[j]]=c;
}
void solve()
{
	int s,i,j,k;
 
	for(s=1;s<=N;s++) //pentru fiecare s
	{
		//reset
		for(i=1;i<=N;i++)
			for(j=1;j<=N;j++)
				a[i][j]=(i >= s && j >= s && ori[i][j]) ? ori[i][j] : INF;
		//floyd-warshall
		for(k=s;k<=N;k++)
		{
			for(i=s;i<=N;i++)
				if(a[i][k]<=INF)
					for(j=s;j<=N;j++)	
						if(a[i][j] > a[i][k] + a[k][j])	
							a[i][j]=a[i][k]+a[k][j];
			//daca avem intre s si k T-ul cautat
			for(i=s;i<=k;i++)
				for(j=s;j<=k;j++)
					if(a[i][j]==T)
					{
						start = NN[i]; 
						smin  = n[s]; 
						end   = NN[j];
						smax  = n[k];
						printf("%d %d %d %d\n",start, end, smin, smax);
						return;
					}
		}
	}		
}

Pentru a aprofunda mai bine acest algoritm va recomand si aceste doua probleme – Rfinv si Roy-Floyd ce sunt mai simplute.