Lucrarea nr. 11

GRAFURI ORIENTATE. APLICATII

1.DEFINITII

In cadrul grafurilor orientate ("directed graphs") arcele sunt orientate, avand un sens precizat.

Grafurile orientate ponderate se mai numesc si "retele" (networks).

2.PROBLEMA DRUMURILOR MINIME CU ORIGINE UNICA. ALGORITMUL LUI DIJKSTRA

Algoritmul lui Dijkstra pentru determinarea drumurilor minime cu origine unica este in principiu asemanator algoritmului prezentat in lucrarea anterioara, de determinarea adrumurilor minime cu origine unica prin cautare bazata pe prioritate.

Se considera un graf orientat ponderat, G=(N,A), fiecarui arc a=(i,j) din A ii este asociat un cost COST[i,j]. Algoritmul utilizeaza o structura de date multime M in care mentine nodurile din N pentru care cea mai scurta distanta pana la nodul origine e deja cunoscuta.Aceasta multime M corespunde multimii nodurior "vizitate" deja. M se initializeaza cu nodul de start.

Algoritmul cuprinde mai multe iteratii, in cadrul fiecarei iteratii se selecteaza un nod x din multimea N-M, cu proprietatea ca x este cel mai aproape de nodul de start si se trece in multimea M a nodurilor vizitate. Se verifica apoi pentru fiecare nod y ramas in N-M daca nu exista un drum mai scurt de la nodul origine spre y, drum care trece prin x.

Algoritmul utilizeaza un tablou D, D[i] fiind lungimea celui mai scurt drum de la origine la nodul numarul i la un moment dat. Initial, D[i]=COST[origine,i]. Pe masura ce se gasesc noduri x,y astfel incat D[y]>D[x]+COST[x,y], D[y] este redus. La terminarea algoritmului, D[i] va contine lungimea drumului minim de la origine la i.

procedure Dijkstra;
  {Date de intrare: Graful orientat ponderat  G=(N,A) si nodul
           nod_origine}
  {Date de iesire: pentru fiecare nod i, D[i] este lungimea
           calculata a drumului minim de la nod_origine la i}
  begin
    * initializeaza multimea M a nodurilor vizitate, introduce nod_origine in M
    * pentru toate nodurile i, initializeaza lungimea drumului minim pana la i
               (D[i]) cu lungimea arcului direct de la nod_origine la i
    while ( * mai exista noduri in N-M ) do
          begin
               *  alege un nod x apartinand multimii N - M astfel incat D[x] sa fie
                   minim si il adauga pe x la M;
               for * fiecare nod y din N-M  do
                   *  test daca drumul de la nod_origine la y folosind ca punct
                    intermediar  nodul x este mai scurt decit  cel memorat
                    anterior, si daca da, actualizeaza D[y] in forma
                    D[y] := min(D[y],D[x] + COST[x,y]);
          end
  end; {Dijkstra}

In vederea reconstructiei traseurilor drumurilor minime de la nodul de start la fiecare nod al grafului, se poate utiliza un alt tablou Parinte de noduri, in care Parinte[x] contine nodul care precede nodul x in cadrul drumului minim. Initial, Parinte[i]= 1 pentru toate nodurile, cu exceptia nodului 1(nodul de start). Elementul Parinte[y] va fi actualizat in momentul actualizarii lui D[y], daca D[x]+COST[x,y] Problema determinarii drumurilor minime corespunzatoare unui nod precizat al unui graf se reduce de fapt la determinarea unui arbore de acoperire care are drept radacina nodul in cauza.

Algoritmul lui Dijkstra opereaza asupra grafurilor dense orientate, reprezentate prin matrici de adiacenta. Se executa n iteratii pentru selectarea tutoror nodurilor, iar in cadrul fiecarei iteratii se face o parcurgere a tuturor nodurilor inca neselectate y pentru ajustarea tabloului D. Performanta algoritmului este deci O(n2).

Daca a este mult mai mic decat n2, este mai indicat ca in reprezentarea grafului sa se foloseasca liste de adiacente, respectiv o coada bazata pe prioritate pentru a pastra nodurile multimii N-M. In acest caz, algoritmul lui Dijkstra devine algoritmul de determinare a drumurilor minime cu origine unica folosind cautarea bazata pe prioritate, prezentat in lucrarea anterioara.

3.PROBLEMA DRUMURILOR MINIME CORESPUNZATOARE TUTUROR PERECHILOR DE NODURI. ALGORITMUL LUI FLOYD

Se considera un graf orientat G=(N,A), in care fiecare arc a=(i,j) din A are o pondere pozitiva COST[i,j]. Problema drumurilor minime corespunzatoare tuturor perechilor de noduri presupune determinarea, pentru fiecare pereche ordonata (i,j), a lungmii drumului minim care conecteaza i cu j.

O rezolvare a acestei probleme este aplicarea repetata a algoritmului lui Dijkstra avand ca nod origine fiecare nod al grafului.

O alta metoda de rezolvare directa a acestei probleme este data de algoritmul lui Floyd.

Fig.1

Algoritmul utilizeaza o matrice A de dimensiuni NxN, in care A[i,j] va fi lungimea drumului minim de la i la j. Initial, se presupune ca drumul minim de la i la j este arcul (i,j). Se testeaza apoi fiecare nod k al grafului, pentru a vedea daca pentru fiecare pereche de noduri i,j nu exista un drum mai scurt de la i la j trecand prin k (figura 1), adica daca suma drumurilor minime de la i la k si de la k la j nu este mai mica decat drumul considerat minim de la i la j. Pentru a determina traseele drumurilor minime, se poate introduce o matrice Drum de dimeniune NxN, Drum[i,j] memoreaza acel nod k care conduce in cadrul algoritmului la scurtarea drumului A[i,j]. Se va alege o valoare speciala pentru "nod inexistent". Daca Drum[i,j]=nod inexistent, atunci cel mai scurt drum de la i la j este arcul direct.

procedure  Floyd;
  {Date de intrare: Graful orientat ponderat G=(N,A)}
  {Date de iesire: pentru fiecare pereche de noduri i,j se
   calculeaza A[i,j]=lungimea drumului minim de la i la j,
   si Drum[i,j]=un nod intermediar pe traseu de la i la j}

  begin
    * initializeaza matricea lungimilor  drumurilor minime  A[i,j]) si matricea
       nodurilor intermediare de pe trasee (Drum[i,j]) presupunand ca drumul minim
       intre  oricare doua  noduri este arcul direct
   for * fiecare nod k al grafului do
       for * fiecare pereche de noduri i,j do
            if (* suma drumurilor de la i la k  si de la k  la j e mai mica decat
                   drumul de la i la j ( A[i,k] + A[k,j] < A[i,j] ))   then
		      begin
                         * actualizeaza valoarea drumului minim, prin
                                        A[i,j] := A[i,k] + A[k,j]
                         * memoreaza punctul de pe traseu, Drum[i,j] := k
	               end
  end; {Floyd}


Pentru reconstituirea traseelor, se poate folosi urmatorul algoritm recursiv.
Algoritmul afiseaza traseul drumului minim intre intre doua noduri specificate,
nodurile i si j.


procedure Traseu(i,j:integer);
  {Date de intrare: nodurile i si j si matricea Drum calculata
                    de algoritmul lui Floyd}
  {Date de iesire:  afiseaza in ordine nodurile intermediare de
                    pe traseul drumului minim de la i la j}
  begin
     if ( *exista cel putin un nod k=Drum[i,j] intermediar de la i la j) then
	    begin
	          Traseu(i,k);
		  writeln(k);
		  Traseu(k,j);
	    end;
  end; { Traseu }

Timpul de executie al algoritmului lui Floyd este de ordinul O(n3).

In timp ce versiunea algoritmului lui Dijkstra determina drumurile minime cu origine comuna in O(n2) in cazul grafurilor dense implementate prin matrici de adiacente, deci aplicarea de n ori a procedurii Dijkstra duce la o performanta O(n3),in cazul grafurilor rare reprezentate prin liste de adiacenta, algoritmul lui Dijkstra este de ordinul O(a log n), deci aflarea tuturor drumurilor minime se poate face cu o performanta O(a n log n).

4.TRAVERSAREA GRAFURILOR ORIENTATE

Cele doua tehnici fundamentale de traversare a grafurilor (cautartea in adancime si cautarea prin cuprindere), prezentate intr-o lucrare anterioara au un caracter general si pot fi aplicate si in cazul grafurilor orientate, tinand cont, in timpul traversarii, de orientarea arcelor examinate.

5.GRAFURI ORIENTATE ACICLICE. SORTAREA TOPOLOGICA

Aceste grafuri pot fi considerate ca o categorie aparte, situata intre arbori si grafurile orientate. Grafurile orientate aciclice pot fi utilizate pentru a reprezenta relatii de ordonare partiala.

Fie M o multime si M * M multimea tuturor perechilor ordonate de elemente din M. O relatie R pe multimea M este o submultime a lui M * M. O relatie R este o relatie de ordine partiala daca este reflexiva, tranzitiva si antisimetrica. Pot exista elemente a,biM care nu pot fi comparate ( nu sunt adevarate nici una din propozitiile (a R b) sau (b R a)

In cadrul unui graf orientat aciclic, se poate defini o relatie de ordine partiala. Fie N multimea nodurilor grafului. Se defineste relatia de ordine partiala R pe multimea N in felul urmator: pentru nodurile u,v din N, se spune ca u R v daca exista un drum in graf de la u la v.

Sortarea topologica a elementelor uiN presupune alcatuirea unei secvente continand toate elementele din N, astfel incat nici care doua elemente consecutive sa nu incalce relatia de ordine partiala. Oricare doua elemente consecutive din secventa sunt in relatia R sau intre ele nu este definita nici o relatie.

Fig. 2

Exemplu: Se considera graful din figura 2. Exista mai multe secvente ce pot reprezenta o ordine de sortare topologica a nodurilor sale.
1 , 2 , 3 , 4
2 , 3 , 1 , 4
2 , 1 , 3 , 4

Sortarea topologica are numeroase aplicatii practice, in diverse situatii de planificare a unor activitati.

Un algoritm de sortare topologica , adaptare a algoritmului de cautare in adancime, este prezentat in continuare.

procedure SortTopologic (x:Nod);
   {Date de intrare: Graful G=(N,A) si nodul de start pentru
                     algoritm, x}
   {Date de iesire: afiseaza nodurile accesibile din x, in
                    ordine topologica  inversa }
  begin
   *  marcheaza nodul x ca vizitat;
   for (*fiecare nod k adiacent lui x) do
        if (*k este nevizitat) then
               SortTopologic(k); { apeleaza recursiv procedura
                              de parcurgere SortTopologic cu nodul de start k}
   writeln(x); {se obs. ca, spre deosebire de alg de cautare
               in adincime, prelucrarea nodului  nu se face la
               vizitare, ci la revenirea din apelul recursiv}
 end; { SortTopologic }

Afisarea (prelucrarea, memorarea) nodurilor se face in ordine topologica inversa. Daca aplicatia necesita ordinea topologica directa, se poate face memorarea nodurilor intr-o stiva, urmand a fi apoi extrase din stiva si prelucrate in ordinea buna. Spre deosebire de algoritmul de cautare in adancime, algoritmul de sortare topologica realizeaza afisarea la revenirea din apelul recursiv de cautare in adancime, si nu la vizitarea nodului. Algoritmul original de cautare in adancime nu produce in general o secventa in ordine topologica, numai in unele cazuri particulare. De exemplu, pentru graful din figura 2, cautarea in adancime produce secventa:
1 , 4 ; 2 , 3 ;

Algoritmul de sortare topologica produce secventa:
4 , 1 ; 3 , 2 ;

Inversul ei este
2 , 3 , 1 , 4
ceea ce este o secventa ordonata topologic.