Drumuri minime si maxime cu grafuri orientate

Trimis la data: 2003-01-27
Materia: Informatica
Nivel: Liceu
Pagini: 5
Nota: 7.24 / 10
Downloads: 10508
Autor: Alina Musat
Dimensiune: 0kb
Voturi: 628
Tipul fisierelor: doc
Acorda si tu o nota acestui referat:
Drumuri minime si maxime cu grafuri orientate - 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.
Drumuri minime si maxime cu grafuri orientate - 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]
Home | Termeni si conditii | Politica de confidentialitate | Cookies | Help (F.A.Q.) | Contact | Publicitate
Toate imaginile, textele sau alte materiale prezentate pe site sunt proprietatea referat.ro fiind interzisa reproducerea integrala sau partiala a continutului acestui site pe alte siteuri sau in orice alta forma fara acordul scris al referat.ro. Va rugam sa consultati Termenii si conditiile de utilizare a site-ului. Informati-va despre Politica de confidentialitate. Daca aveti intrebari sau sugestii care pot ajuta la dezvoltarea site-ului va rugam sa ne scrieti la adresa webmaster@referat.ro.