Referat Drumuri Minime Si Maxime

Mai jos puteti citi fragmente din Referat Drumuri Minime Si Maxime si de asemenea puteti face Download Referat Drumuri minime si maxime

Citeste fragmente din Referat Drumuri Minime Si Maxime

Drumuri minime si maxime 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]i) and(k<>j) then if Dm[i,k]+Dm[k,j]