Acasa | Trimite referat | Cere referat | Contact

Referat Drumuri minime si maxime

Drumuri minime si maxime

Categorie: Referate Informatica

Referat downloadat de: 310 ori.

Cauta referat dupa: drumuri minime maxime

Descriere referat:

Consider?m un graf orientat G=(X,U) cu n noduri, �n care fiec?rui arc �i este asociat un num?r �ntreg numit cost. Semnifica?ia acestui cost poate fi foarte variat?, �n func?ie de domeniul pe care �l descrie graful. De exemplu, dac? graful reprezint? harta unui ora? �n care arcele sunt str?zile iar nodurile sunt intersec?iile dintre st?yi, atunci putem vorbi despre costul deplas?rii unui automobil �ntre dou? intersec?ii, de-a lungul unei str?zi. Acesta s-ar putea m?sura �n cantitatea de benzin? consumat?, calculat? prin prisma lungimii str?zii �n m sau in km. Pentru eviden?ierea costurilor tuturor arcelor unui graf cu n noduri se poate defini o matrice a, cu n linii *n coloane.exist? dou? forme ale acestei matrici: Forma a): Fiecare element a[i,j] poate fi: -c, dac? exist? un arc de cost c>0 �ntre nodurile i ?i j; -0, dac? i=j; -+?, dac? nu exist? arc �ntre nodurile i ?i j. Forma b): Este absolut similar?, cu singura deosebire c? �n loc de +? avem -?. Forma a)se folose?te pentru determinarea drumurilor de cost minim �ntre dou? noduri, iar forma b) este utilizat? �n aflarea drumurilor de cost maxim. Dac? dorim s? citim matricea costurilor, evident c? nu putem introduce de la tastatur? �+?�! �n loc de �+?� vom da un num[r de la tastatur? foarte mare. Problema determin?rii drumului minim/ maxim �ntre dou? noduri face obiectul algoritmului urm?tor. Algoritmul Roy-Floyd Se consider? un graf orientat cu n noduri, pentru care se d? matricea costurilor �n forma a). Se cere ca, pentru fiecare pereche de noduri (i, j), s? se tip?reasc? costu drumului minim de la i la j. Plec?m de la urm?toarea idee: dac? drumul minim �ntre dou? noduri oarecare i ?i j trece printr-un nod k, atunci drumurile de la i la k ?i de la k la j sunt la r�ndul lor minime. Pentru fiecare pereche de noduri (i, j ), cu i, j ?{1,2,�,n}, proced?m astfel: � D?m lui k pe r�nd valorile 1,2,�,n, pentru ca nodul k despre care vorbeam mai sus poate fi, cel pu?in teoretic, orice nod al grafului. Pentru fiecare k: ? dac? suma dintre costul drumului de la i la j ?i costul drumului de la k la j este mai mic? dec�t costul drumului de la i la j {a[i, k]+a[k, j]

Alte referate din materia: Informatica

Nr.	Nume referat	Hits
1	mtSZPKbW	20
2	TkkvMlabSupl	50
3	qzpymq@dxuzju.com	147
4	email@gmail.com	268
5	pfuqxd@exjswl.com	287
6	ncqcez@hdtnnq.com	244
7	Hard	722
8	ISTORIA INTERNET-ULUI	782
9	Impera	469
10	Info Doc	524
11	Info-TIRON	467
12	Informatica - Grafica pentru web	938
13	Informatica - Introducere in HTML	711
14	Initiere in pc	701
15	Instalarea sistemului de operare Windows	593
16	Internetul ca sursa de comunicare	580
17	Istoria Internetului	617
18	Istoria calculatorului	539
19	Istoria metodelor de proiectare	359
20	Java visavis de C++	401
21	Java vizavi de C	333
22	LIMBAJUL DE PROGRAMARE PASCAL - Programul defineste tipul salariat, o inregistrare cu variante, valorile citite fiind salvate in fisierul salariat.dat	0
23	Limbajul C	413
24	Lista vinuri prg	322
25	Lotus software	293

Acasa Trimite referat Cere referat Adauga la favorite Seteaza ca homepage Contact libertateailuziei Trailere Filme Filme Noi Jocuri Online Jocuri Barbie Jocuri pentru Copii GameBox.ro Make Money Bucuresti regim hotelier