Document, comentariu, eseu, bacalaureat, liceu si facultate
Top documenteAdmitereTesteUtileContact
      
    


 


Ultimele referate adaugate

Adauga referat - poti sa ne ajuti cu un referat?

Politica de confidentialitate



Ultimele referate descarcare de pe site
  CREDITUL IPOTECAR PENTRU INVESTITII IMOBILIARE (economie)
  Comertul cu amanuntul (economie)
  IDENTIFICAREA CRIMINALISTICA (drept)
  Mecanismul motor, Biela, organe mobile proiect (diverse)
  O scrisoare pierduta (romana)
  O scrisoare pierduta (romana)
  Ion DRUTA (romana)
  COMPORTAMENT PROSOCIAL-COMPORTAMENT ANTISOCIAL (psihologie)
  COMPORTAMENT PROSOCIAL-COMPORTAMENT ANTISOCIAL (psihologie)
  Starea civila (geografie)
 

Ultimele referate cautate in site
   domnisoara hus
   legume
    istoria unui galban
   metanol
   recapitulare
   profitul
   caract
   comentariu liric
   radiolocatia
   praslea cel voinic si merele da aur
 
despre:
 
Grafuri
Colt dreapta
Vizite: ? Nota: ? Ce reprezinta? Intrebari si raspunsuri
 
f3n4nm
Consideram un graf orientat G=(X,U) cu n noduri, in care fiecarui arc ii este asociat un numar intreg numit cost. Semnificatia acestui cost poate fi foarte variata, in functie de domeniul pe care il descrie graful. De exemplu, daca graful reprezinta harta unui oras in care arcele sunt strazile iar nodurile sunt intersectiile dintre stayi, atunci putem vorbi despre costul deplasarii unui automobil intre doua intersectii, de-a lungul unei strazi. Acesta s-ar putea masura in cantitatea de benzina consumata, calculata prin prisma lungimii strazii in m sau in km.

Pentru evidentierea costurilor tuturor arcelor unui graf cu n noduri se poate defini o matrice a, cu n linii *n coloane.exista doua forme ale acestei matrici:
Forma a): Fiecare element aai,ji poate fi:
-c, daca exista un arc de cost c>0 intre nodurile i si j;
-0, daca i=j;
-+¥, daca nu exista arc intre nodurile i si j.
Forma b): Este absolut similara, cu singura deosebire ca in loc de +¥ avem -¥.
Forma a)se foloseste pentru determinarea drumurilor de cost minim intre doua noduri, iar forma b) este utilizata in aflarea drumurilor de cost maxim.
Daca dorim sa citim matricea costurilor, evident ca nu putem introduce de la tastatura “+¥”! In loc de “+¥” vom da un numar de la tastatura foarte mare.
Problema determinarii drumului minim/ maxim intre doua noduri face obiectul algoritmului urmator.

Algoritmul Roy-Floyd
Se considera un graf orientat cu n noduri, pentru care se da matricea costurilor in forma a). Se cere ca, pentru fiecare pereche de noduri (i, j), sa se tipareasca costu drumului minim de la i la j.
Plecam de la urmatoarea idee: daca drumul minim intre doua noduri oarecare i si j trece printr-un nod k, atunci drumurile de la i la k si de la k la j sunt la randul lor minime. Pentru fiecare pereche de noduri (i, j ), cu i, j IA1,2,…,nS, procedam astfel:
· Dam lui k pe rand valorile 1,2,…,n, pentru ca nodul k despre care vorbeam mai sus poate fi, cel putin teoretic, orice nod al grafului. Pentru fiecare k:
Ø daca suma dintre costul drumului de la i la j si costul drumului de la k la j este mai mica decat costul drumului de la i la j Aaai, ki+aak, ji<aai, jiS, atunci drumul initial de la i la j este inlocuit cu drumul indirect i®k®j. aceasta inlocuire fireste ca se va opera ca atare in matrocea costurilor: Aaai, ji:=aai, ki+aak, jiS.
Prezentam in continuare procedura generare care contine algoritmul descris:
Procedure generare; var i,j,k:integer; begin for k:=1 to n do for i:=1 to n do for j:=1 to n do if aai, ki+aak, ji<aai, ji then aai, ji:=aai, ki+aak, ji; end;




Ø Drumurile minime intre toate nodurile se regasesc la finele algoritmului tot in matricea costurilor, care a suferit n trasformari, pentru k=1,2,…,n.
Ø Unele elemente pot fi +¥, iar pentru simularea lui +¥ am spus ca se introduce un numar intreg foarte mare. Prin adunari repetate a doua numere intregi foarte mari putem ajunge la un rezultat care depaseste cea mai mare valoare posibila de tipul integer. De aceea, recomandam ca elementele matricei costurilor sa fie de tipul longint.
Ø In cazul in care problema cerea pentru fiecare pereche de noduri (i, j) costul drumului maxim, modificarile necesare ar fi minore:
- se foloseste forma b) a matricei costurilor;
- conditia testata in linia if devine “aai, ki+aak, ji<aai, ji”

program drummax; uses crt; type matr=arraya1..20,1..20iof integer; var C,a:matr; f:text; n:integer;
Procedure citire(var c:matr;var n:integer); var a:matr; i,j:integer;
Begin assign(f,'costgraf.txt'); reset(f); readln(f,n);
For i:=1 to n do
For j:=1 to n do
Read(f,cai,ji); close(f);
End;
Procedure RF; var i,j,k:integer;
Begin a:=c;
For k:=1 to n do
For i:=1 to n do
For j:=1 to n do
If aai,ki+aak,ji<aai,ji then aai,ji:=aai,ki+aak,ji;
End;
Procedure afisare(x:matr;n:integer); var i,j:integer;
Begin for i:=1 to n do begin for j:=1 to n do
write(xai,ji,' ');
writeln; end; end;
BEGIN clrscr; citire(c,n); afisare(c,n);
RF; afisare(a,n); readkey; end.

program drummin; uses crt; type matr=arraya1..20,1..20iof integer; var c,Dm:matr; Ac=matricea costurilorS n,i,j:integer;
Procedure citire(var c:matr;var n:integer); var f:text; x,m,i,j:integer;
Begin
Assign(f,'cost.txt');
Reset(f);
Readln(f,n);
Readln(f,m); for i:=1 to n do for j:=1 to n do if i=j then cai,ji:=0 else cai,ji:=maxint; for i:=2 to m do begin readln(f,i,j,x); Ax=costS cai,ji:=x; end; close(f);
End;
Procedure minim(var Dm:matr); var i,j,k:integer;
Begin
Dm:=c; for k:=1 to n do for i:=2 to n do for j:=1 to n do if (k<>i) and(k<>j) then if Dmai,ki+Dmak,ji<Dmai,ji then Dmai,ji:=Dmai,ki+Dmak,ji;
End;
BEGIN clrscr; citire(c,n); minim(Dm); for i:=1 to n do begin for j:=1 to n do
Write(Dmai,ji,' ');
writeln; end; readkey; end.


Colt dreapta
Creeaza cont
Comentarii:

Nu ai gasit ce cautai? Crezi ca ceva ne lipseste? Lasa-ti comentariul si incercam sa te ajutam.
Esti satisfacut de calitarea acestui document, eseu, cometariu? Apreciem aprecierile voastre.

Nume (obligatoriu):

Email (obligatoriu, nu va fi publicat):

Site URL (optional):


Comentariile tale: (NO HTML)


Noteaza documentul:
In prezent fisierul este notat cu: ? (media unui numar de ? de note primite).

2345678910

 
Copyright© 2005 - 2024 | Trimite document | Harta site | Adauga in favorite
Colt dreapta