• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Algoritmul Floyd-Warshall pentru determinarea tuturor drumurilor de cost minim

6
  • Publicat de Andrei Avădănei
  • în C/C++
  • — 11 nov., 2010 at 11:30 am

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.

Etichete: algoritmicaC++determinarea drumurilor de cost minimfloyd-warshallgrafuriparcurgere in latimeprogramare dinamicaroy-floydTehnicteoria grafurilor

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior PlayFest 2010 – evenimentul de gaming 3D al anului
  • Articolul următor WorldIT.info se bucura de o noua bariera depasita

6 Comentarii

  1. Adrian spune:
    noiembrie 11, 2010 la 5:37 pm

    Din cate imi amintesc se putea la coach si in O(n^3) daca se facea o observatie, mai dificila evident, ca nu conteaza ambele valori, ci numai una, si folosindu-ne de faptul ca nu trebuie sa facem pentru fiecare nod un roy-floyd, ci putem sorta nodurile dupa energia bauturii. Avand in vedere ca la fiecare pas din roy-floyd incercam sa adaugam nodul curent in lanturile minime dintre noduri, valoare maxima a energiei va creste la fiecare pas sau va ramane egala, pentru fiecare drum minim intre i si j(oricare ar fi i si j de la 1 la n). Astfel se formeaza solutia in O(n^3):
    1)Sortam nodurile dupa valoarea energetica
    2) Aplicam roy-floyd
    3) La fiecare pas in roy-floyd, dupa ce micsoram lanturile, verificam daca avem un lant de lungime T(dureaza T minute) si daca da ne oprim.
    4) Limita inferioara va fi 0 iar cea superioara va fi valoarea energetica a bauturii din orasul la care ne-am oprit in roy-floyd.
    Eu cel putin asa am rezolvat, sper sa ajute pe cineva

  2. Seby spune:
    noiembrie 12, 2010 la 12:25 pm

    Salut . Scuze daca sunt pe langa subiect. Asi avea o intrebare:

    Dupa cum stiti , se pot extrage date dintr-un fisier XML cu ajutorul unui cod PHP care extrage anumite date specificate in codul PHP .. aici referindune la tag-urile de la care vrem sa extragem datele.

    Se poate sa extragem doar anumite date ? De exemplu intr-un fisier XML care contine titlu de haine . Se poate sa extragem din fisierul XML doar datele care contin numele blugi spre exemplu .. sau tricou ?

  3. Andrei Avadanei spune:
    noiembrie 12, 2010 la 1:26 pm

    Raspunsul la intrebarea ta e da. Doar ca nu ai nici o treaba cu acest subiect de aceea nu voi intra in detalii. Vrei mai multe raspunsuri, exista forumul worldit.

  4. Andrey spune:
    noiembrie 12, 2010 la 7:52 pm

    super tare problema :>

  5. skykery spune:
    martie 5, 2011 la 2:59 pm

    Buna ziua, folosesc pluginul WordPress Code Snippet pentru cod si as vrea sa stiu cum pot face sa fie codul mai mic sau textu, exact cum aveti pe acest blog . Ma intereseaza pentru un prieten .

  6. Andrei Avădănei spune:
    martie 5, 2011 la 7:11 pm

    E vorba de font-size din CSS. 🙂


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • august 2022
    L Ma Mi J V S D
    1234567
    891011121314
    15161718192021
    22232425262728
    293031  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Algoritmul Floyd-Warshall pentru determinarea tuturor drumurilor de cost minim
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons