Matricea costurilor si graficele orientate referat





Drumuri minime si maxime in grafuri orientate







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.

A. Matricea costurilor




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 a[i,j] 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 num[r de la tastatura foarte mare.

Problema determinarii drumului minim maxim intre doua noduri face obiectul algoritmului urmator.

Aplicatie


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 I , 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 , 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: .

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 a[i, k]+a[k, j]<a[i, j] then a[i, j]:=a[i, k]+a[k, j];

end;

Observatii



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 “a[i, k]+a[k, j]<a[i, j]”


















Drumuri maxime


program drummax;

uses crt;

type matr=array[1..20,1..20]of 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,c[i,j]);

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 a[i,k]+a[k,j]<a[i,j]

then a[i,j]:=a[i,k]+a[k,j];

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(x[i,j],' ');

writeln;

end;

end;

BEGIN

clrscr;

citire(c,n);

afisare(c,n);

RF;

afisare(a,n);

readkey;

end.


Drumuri minime



program drummin;

uses crt;

type matr=array[1..20,1..20]of integer;

var c,Dm:matr;

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 c[i,j]:=0

else c[i,j]:=maxint;

for i:=2 to m do

begin

readln(f,i,j,x);

c[i,j]:=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 Dm[i,k]+Dm[k,j]<Dm[i,j]

then Dm[i,j]:=Dm[i,k]+Dm[k,j];

End;

BEGIN

clrscr;

citire(c,n);

minim(Dm);

for i:=1 to n do

begin

for j:=1 to n do

Write(Dm[i,j],' ');

writeln;

end;

readkey;

end.











Copyright © Contact | Trimite referat


Ultimele referate adaugate
Mihai Beniuc
   - Mihai beniuc - „poezii"
Mihai Eminescu Mihai Eminescu
   - Mihai eminescu - student la berlin
Mircea Eliade Mircea Eliade
   - Mircea Eliade - Mioara Nazdravana (mioriţa)
Vasile Alecsandri Vasile Alecsandri
   - Chirita in provintie de Vasile Alecsandri -expunerea subiectului
Emil Girlenu Emil Girlenu
   - Dragoste de viata de Jack London
Ion Luca Caragiale Ion Luca Caragiale
   - Triumful talentului… (reproducere) de Ion Luca Caragiale
Mircea Eliade Mircea Eliade
   - Fantasticul in proza lui Mircea Eliade - La tiganci
Mihai Eminescu Mihai Eminescu
   - „Personalitate creatoare” si „figura a spiritului creator” eminescian
George Calinescu George Calinescu
   - Enigma Otiliei de George Calinescu - geneza, subiectul si tema romanului
Liviu Rebreanu Liviu Rebreanu
   - Arta literara in romanul Ion, - Liviu Rebreanu











Scriitori romani