Grafuri orientate

28
Grafuri orientate Algoritmul lui Dijkstra Elevi: Badea Constantin Cătălin Bădulescu Ştefan Leonard Milotin Gheorghe Cătălin Urs Daniela Vitejanu Vasile Mădălin

description

Grafuri orientate. Elevi: Badea Constantin Cătălin Bădulescu Ştefan Leonard Milotin Gheorghe Cătălin Urs Daniela Vitejanu Vasile Mădălin. Algoritmul lui Dijkstra. - PowerPoint PPT Presentation

Transcript of Grafuri orientate

Page 1: Grafuri  orientate

Grafuri orientate

Algoritmul lui Dijkstra

Elevi:

Badea Constantin CătălinBădulescu Ştefan LeonardMilotin Gheorghe Cătălin

Urs Daniela Vitejanu Vasile Mădălin

Page 2: Grafuri  orientate

După câţiva ani de la terminarea liceului, trei foşti colegi(Bogdan,Alin şi Adrian) se întâlnesc întâmplător pe stradă. Bucuroşi că s-auintâlnit, ei propun să meargă la un suc şi să povestească ce au mai făcut de când nu s-au mai văzut. Din vorbă in vorbă, Bogdan îi intreabă pe ceilalţi doi dacă au un loc de muncă. Alin îi spune că a lucrat timp de doi ani la o firmă care in urmă cu 2 luni dăduse faliment ,că era in şomaj, şi că plănuieşte sa plece in străinătate. Adrian, ii zice că a depus deja cateva CV-uri, dar nu a primit nici un răspuns şi era foarte dezamăgit. După câteva idei despre cum ar putea să câştige bani, mai in glumă, mai in serios, Adrian propune, dat fiind faptul că fiecare deţinea câte un autoturism, să realizeze o firmă de Taxi. Firma mergea bine, insă cei trei erau dezamăgiţi că nu reuşeau să aleagă mereu traseul cel mai scurt. Într-una din zile, Alin şi-a amintit că în timpul liceului la orele de informatică a aflat despre noţiunea de GRAF, pe care pentru a o înţelege, îşi imagina Graful ca fiind reţeaua de străzi a unui oraş, in care intersecţiile erau echivalentul nodurilor din graf, iar străzile echivalentul arcelor grafului. Plecând de la această idee, Alin a încercat să realizeze un program, in MinGW, care calculează drumurile minime de la un nod al unui graf la cel care trebuia sa fie nodul final din graf . După ce şi-a amintit toate acestea,Alin a intrat pe internet si a descoperit că există un algoritm care realizează ceea de ce el avea nevoie. Acel algoritm numindu-se Algoritmul lui Dijkstra .

Page 3: Grafuri  orientate

Pentru a şti mult mai bine ce au de făcut cu acel algortim, el a căutat şi cateva definiţii generale despre grafurile orientate, aşa ca el şi-a amintit urmatoarele :● Un graf orientat este o pereche ordonată de mulţimi, notată G=(X,U), undeX={x|xX} este mulţimea nodurilor (vârfurilor) iar U={(x,y)| x,yX}, mulţimea arcelor● Drum este o succesiune de noduri cu proprietatea că oricare două noduri consecutive sunt adiacente(arcele pastrează aceeaşi orientare)

* drum simplu = drum în care fiecare arc apare o singură dată dar nodurile se pot repeta* drum elementar = drum în care nodurile sunt distincte

● Un graf conex reprezintă un graf în care oricare ar fi două noduri distincte, există lanţ(succesiune de noduri cu proprietatea că oricare două noduri consecutive din lanţ sunt adiacente) între ele.● Se numeste graf ponderat ("weighted graph") un graf in cadrul căruia fiecărui arc îi este asociată o valoare. Valoarea asociată arcului are semnificaţia de "cost" a legaturii între cele 2 noduri sau de "distanţa" intre noduri.● Prin modurile de reprezentare ale grafurilor orientate se numară : * Matricea de adiacentă: este o matrice patratică cu n linii si n coloane, in care elementele a[i,j] se definesc astfel: a[i,j]=1 dacă există arcul (i,j) în U, cu x diferit de y şi 0 daca nu există arcul (i,j) in U. * Matricea de incidenţă este o matrice cu n linii (numărul vârfurilor) şi m coloane (numărul arcelor), notate cu uj, în ordineaîn care apar în mulţimea L. Elementele sunt definite astfel : a i,j = 1, dacă [i,j] sunt incluse în U, sau a i,j =0, altfel * Lista muchiilor unui graf este formată din m elemente care conţin , fiecare, cate o pereche de doua noduri , xi şi xj, care formeaza o muchie, adică pentru care [xi, xj] aparţin lui U. * Lista de adiacentă este formată din listele Li care conţin toţi vecinii unui nod xi la care se poate ajunge direct din nodul xi, adică toate nodurile xj pentru care [xi, xj]aparţin lui U. * Matricea costurilor

Page 4: Grafuri  orientate

Grafurile pe care poate lucra algoritmul lui Dijkstra sunt, în general, ponderate si orientate . • Dacă graful este neponderat (arcele nu au costuri asociate) atunci

drum minim între două noduri se consideră drumul alcătuit din număr minim de arce.

• Pentru a găsi drumul minim de la un nod X la un nod Y se poate aplica o căutare prin cuprindere pornind de la nodul X – prima apariţie a lui Y în coada algoritmului de căutare prin cuprindere presupune existenţa unui drum cu număr minim de arce de la X la Y, care poate fi reconstituit.

• Pe un astfel de graf se poate aplica si algoritmul lui Dijkstra, dacă transformăm în prealabil graful într-unul ponderat, asociind fiecărui arc acelasi cost.

• Drumul de cost minim intre două noduri obţinut în urma aplicării algoritmului lui Dijkstra va avea şi număr minim de arce din moment ce toate arcele au acelasi cost.

• Algoritmul lui Dijkstra funcţionează atât pe grafuri conexe cât si

pe grafuri neconexe.• Dacă nu există nici un drum de la nodul de start la un alt nod al

grafului atunci algoritmul lui Dijkstra va raporta existenţa unui drum de lungime infinită între ele – acest rezultat indică, de fapt, lipsa oricărui drum între cele două noduri.

Page 5: Grafuri  orientate

• Intrare:– Algoritmul porneşte de la un graf orientat şi ponderat cu N

noduri.– De asemenea, e nevoie de un nod de start aparţinând

grafului – acesta este nodul de la care se doreşte aflarea drumurilor minime până la celelalte noduri din graf.

• Iesire:– Rezultatul algoritmului se prezintă sub forma unui tablou D

cu N intrări, conţinând distanţele minime de la nodul de start la toate celelalte noduri din graf.

– De asemenea, tot ca rezultat se poate obţine si arborele drumurilor minime (în cazul în care ne interesează nu numai lungimile minime ale drumurilor, ci şi drumurile propriu-zise) – acesta este un arbore generalizat care se va obţine sub forma unui tablou T cu N intrări (implementarea cu indicatori spre părinte)

• Fie X nodul de start – acesta se marchează ca vizitat• Ideea găsirii drumului minim de la X la un un alt nod este

căutarea treptată: se presupune că drumul minim este alcătuit dintr-un singur arc (arcul direct între X si nodul ţinta, care poate sa nu existe, costul său fiind infinit in acest caz), apoi se caută drumuri mai scurte alcătuite din 2 arce, apoi din 3, etc. – un drum minim nu poate avea mai mult de N-1 arce, deci algoritmul are N-1 pasi (al N-lea este banal)

• După pasul k (1 ≤ k ≤ N-1), tabloul D va conţine lungimile drumurilor minime de la nodul X la celelalte noduri, toate aceste drumuri fiind alcătuite din maxim k arce.

• Astfel, D[Y] = L după pasul k înseamnă că de la X la Y există un drum minim de lungime L alcătuit din maxim k arce

• Deci, după pasul k, au fost găsite numai drumurile minime alcătuite din maxim k arce – abia la finalul algoritmului (dupa pasul N-1) drumurile minime obţinute sunt definitive, ele fiind drumuri minime alcătuite din maxim N-1 arce.

Page 6: Grafuri  orientate

• La începutul fiecărui pas k avem un set de k-1 noduri marcate (in cadrul pasilor precedenţi) – nodurile marcate sunt cele pentru care se cunoaste drumul minim (initial, doar nodul de start este marcat deoarece doar pentru el se cunoaşte drumul minim)

• In cadrul pasului k trebuie executate 3 operatiuni:– Se găseste acel nod Y nemarcat care are D[Y] minim (acesta

este singurul dintre nodurile nemarcate pentru care se poate spune sigur că drumul minim are lungimea D[Y]) – pentru celelalte noduri nemarcate valoarea corespunzătoare din tabloul D s-ar putea să nu reprezinte lungimea drumului minim ci un drum minim intermediar (alcătuit din maxim k-1 arce) care poate fi imbunătăţit in cadrul paşilor viitori ai algoritmului

– Nodul Y se marchează ca vizitatLogica este următoarea:D[Y] conţine lungimea drumului minim de la nodul de start la nodul Y care trece numai prin noduri marcate (Y fiind, la inceputul pasului k, nodul nemarcat care avea D[Y] minim) – acest drum este alcătuit din maxim k-1 arce – D[Y] fiind minim, il marcam pe Y deoarece nu poate exista un drum mai scurt de la X la YD[Z] conţine lungimea celui mai scurt drum de la nodul de start la nodul Z alcătuit din maxim k-1 arce – acest drum trece doar prin noduri marcate, fără să ţină cont că, între timp, şi Y a fost marcat.S-ar putea sa existe un drum mai scurt decât D[Z] de la nodul de start la Z alcătuit din maxim k arce care trece numai prin noduri marcate, inclusiv nodul Y – unicul drum cu această proprietate care poate fi mai scurt decât D[Z] este cel care include drumul minim până la Y si arcul direct intre Y si Z, deci lungimea sa este D[Y] + Arc(Y , Z)

Page 7: Grafuri  orientate

EXEMPLU:Fie graful din figura:

Vrem să aflăm drumurile minime de la nodul A la nodul H.

91

4

9

3

1

25

14

1 2

A

B

C

D

EF

G

H

5

Page 8: Grafuri  orientate

Algoritmul trebuie să returneze urmatorul rezultat: D =

T =

Tabloul D are câte o intrare pentru fiecare nod al grafului, corespunzând lungimii drumului minim de la nodul A până la respectivul nod.Astfel, drumul minim de la A la A nu interesează (-), drumul minim de la A la F are lungimea 4, drumul minim de la A la H nu exista (∞), etc.

- 7 1 3 3 4 5 ∞

A B C D E F G H

A E A A C E F -

Page 9: Grafuri  orientate

• A este nodul de start – îl marcăm ca vizitat• Fiind primul pas, initializăm tablourile D si T astfel:

– D[x] este lungimea arcului direct de la A la nodul x pentru fiecare nod x.– T[x] este nodul de start (sau indicele nodului de start in T – dacă se doreşte un tablou de indicatori

spre părinte clasic).

- 9 1 3 ∞ ∞ 9 ∞

A B C D E F G H

A A A A A A A

D:

T: A

91

4

9

3

1

25

14

1 2

A

B

C

D

EF

G5

HNodurile marcate astfel sunt noduri vizitate in graf de algoritmul lui

Dijkstra

Page 10: Grafuri  orientate

• Cu alte cuvinte, presupunem că drumurile minime de la nodul A la celelalte noduri din graf sunt alcătuite dintr-un singur arc, adică arcul direct de la A la fiecare din nodurile respective (simbolul ∞ semnifică lipsa arcului)

• Astfel, drumurile minime găsite după primul pas sunt cele îngrosate pe figura anterioară

• Se alege nodul C şi se marchează, deoarece nodul C este nodul nemarcat care are intrarea in tabloul D minimă – drumul minim de la A la C are lungimea 1 (nu vom găsi altul mai scurt până la final).

91

4

9

3

1

25

14

1 2

B

C

D

EF

G

H

5

- 9 1 3 ∞ ∞ 9 ∞

A B C D E F G H

D:

A

Page 11: Grafuri  orientate

9 1 3 ∞ ∞ 9 ∞

A B C D E F G H

• Tabloul D este:

• Pentru toate nodurile nemarcate trebuie să verificăm dacă nu există un drum mai scurt care trece prin nodul C

• Exemplu pentru nodul B:– D[B] = 9 este drumul cel mai scurt de la A la B pe care-l aveam.– D[C] + Arc(C , B) = 1 + ∞ = ∞ este drumul alternativ care trece prin nodul C (nodul

ales).– Acest al doilea drum este mai lung decât drumul pe care-l aveam deci D[B] nu se

modifică la acest pas.

• Exemplu pentru nodul E:– D[E] = ∞ este drumul cel mai scurt de la A la E pe care-l aveam.– D[C] + Arc(C , E) = 1 + 2 = 3 este drumul alternativ care trece prin nodul C (nodul

ales).– Deoarece noul drum este mai scurt decât drumul pe care-l aveam rezultă că D[E] se

modifică din ∞ in 3 şi T[E] se modifică in C (nodul ales).– Se observă că drumul alternativ trece prin nodul C (nodul ales).– Drumul de la A la C de lungime D[C] fiind minim, dacă adaugăm arcul C->E obţinem

obligatoriu drumul minim de la A la E care trece prin C.

-

Page 12: Grafuri  orientate

• Procedând la fel pentru toate nodurile nemarcate, obţinem urmatorul rezultat:

D

91

4

9

3

1

25

1

4

1 2

A

B

C

EF

G

H

5

- 9 1 3 3 6 9 ∞

A B C D E F G H

A A A A C C A A

D:

T:

Din nodul C au fost descoperite aceste 2

drumuri noi (mai scurte) catre E si F

Page 13: Grafuri  orientate

• Se alege nodul D şi se marchează, deoarece nodul D are intrarea în tabloul D minimă (chiar dacă egală cu intrarea nodului E, alegerea este arbitrară) – drumul minim de la A la D are lungimea 3 (nu vom găsi altul mai scurt până la final)

- 9 1 3 3 6 9 ∞

B C D E F G H

D:

91

4

9

3

1

25

14

1 2

A

B

C

D

EF

G

H

5

Page 14: Grafuri  orientate

• Tabloul D este:

• Pentru toate nodurile nemarcate trebuie să verificăm dacă nu există un drum mai scurt care trece prin nodul D

• Exemplu pentru nodul F:– D[F] = 6 este drumul cel mai scurt de la A la F pe care-l aveam.– D[D] + Arc(D , F) = 3 + ∞ = ∞ este drumul alternativ care trece prin nodul D (nodul

ales).– Acest al doilea drum este mai lung decât drumul pe care-l aveam deci D[F] nu se

modifică la acest pas.• Exemplu pentru nodul G:

– D[G] = 9 este drumul cel mai scurt de la A la G pe care-l aveam.– D[D] + Arc(D , G) = 3 + 5 = 8 este drumul alternativ care trece prin nodul D (nodul

ales).– Deoarece noul drum este mai scurt decât drumul pe care-l aveam rezultă că D[G]

se modifică din 9 în 8 şi T[G] se modifică în D (nodul ales).– Se observă că drumul alternativ trece prin nodul D (nodul ales).– Drumul de la A la D de lungime D[D] fiind minim, dacă adaugăm arcul D->G

obţinem obligatoriu drumul minim de la A la G care trece prin D.

9 1 3 3 6 9 ∞

A B C D E F G H

-

Page 15: Grafuri  orientate

• Procedând la fel pentru toate nodurile nemarcate, obţinem următorul rezultat:

91

4

9

3

1

25

14

1 2

A

B

C

D

EF

G

H

5

- 9 1 3 3 6 8 ∞

A B C D E F G H

A A A A C C D A

D:

T:

Din nodul D a fost descoperit acest drum nou (mai scurt) catre G

Page 16: Grafuri  orientate

• Se alege nodul E şi se marchează, deoarece nodul E are intrarea în tabloul D minimă – drumul minim de la A la E are lungimea 3 (nu vom găsi altul mai scurt până la final)

- 9 1 3 3 6 8 ∞

A B C D E F G H

D:

91

4

9

3

1

25

14

1 2

A

B

C

D

EF

G

H

5

Page 17: Grafuri  orientate

• Tabloul D este:

• Pentru toate nodurile nemarcate trebuie să verificăm dacă nu există un drum mai scurt care trece prin nodul E.

• Exemplu pentru nodul G:– D[G] = 8 este drumul cel mai scurt de la A la G pe care-l

aveam.– D[E] + Arc(E , G) = 3 + ∞ = ∞ este drumul alternativ care trece

prin nodul E (nodul ales).– Acest al doilea drum este mai lung decât drumul pe care-l

aveam deci D[G] nu se modifică la acest pas.• Exemplu pentru nodul B:

– D[B] = 9 este drumul cel mai scurt de la A la B pe care-l aveam.– D[E] + Arc(E , B) = 3 + 4 = 7 este drumul alternativ care trece

prin nodul E (nodul ales).– Deoarece noul drum este mai scurt decât drumul pe care-l

aveam rezultă că D[B] se modifică din 9 în 7 şi T[B] se modifică în E (nodul ales).

– Se observă că drumul alternativ trece prin nodul E (nodul ales).– Drumul de la A la E de lungime D[E] fiind minim, dacă adaugăm

arcul E->B obţinem obligatoriu drumul minim de la A la B care trece prin E.

- 9 1 3 3 6 8 ∞

A B C D E F G H

Page 18: Grafuri  orientate

• Procedând la fel pentru toate nodurile nemarcate, obtinem urmatorul rezultat:

91

4

9

3

1

25

14

1 2

A

B

C

D

EF

G

H

5

- 7 1 3 3 4 8 ∞

A B C D E F G H

A E A A C E D A

D:

T:

Din nodul E au fost descoperite aceste 2

drumuri noi (mai scurte) catre B si F

Page 19: Grafuri  orientate

• Se alege nodul F şi se marchează, deoarece nodul F are intrarea în tabloul D minimă – drumul minim de la A la F are lungimea 4 (nu vom găsi altul mai scurt până la final).

- 7 1 3 3 4 8 ∞

A B C D E F G H

D:

91

4

9

3

1

25

14

1 2

A

B

C

D

EF

G

H

5

Page 20: Grafuri  orientate

• Tabloul D este:

• Pentru toate nodurile nemarcate trebuie să verificăm dacă nu există un drum mai scurt care trece prin nodul F.

• Exemplu pentru nodul B:– D[B] = 7 este drumul cel mai scurt de la A la B pe care-l

aveam.– D[F] + Arc(F , B) = 4 + ∞ = ∞ este drumul alternativ care

trece prin nodul F (nodul ales).– Acest al doilea drum este mai lung decât drumul pe care-l

aveam deci D[B] nu se modifică la acest pas.• Exemplu pentru nodul G:

– D[G] = 8 este drumul cel mai scurt de la A la G pe care-l aveam.

– D[F] + Arc(F , G) = 4 + 1 = 5 este drumul alternativ care trece prin nodul F (nodul ales).

– Deoarece noul drum este mai scurt decât drumul pe care-l aveam rezultă că D[G] se modifică din 8 în 5 şi T[G] se modifică în F (nodul ales).

– Se observă că drumul alternativ trece prin nodul F (nodul ales).

– Drumul de la A la F de lungime D[F] fiind minim, dacă adaugăm arcul F->G obţinem obligatoriu drumul minim de la A la G care trece prin F.

- 7 1 3 3 4 8 ∞

A B C D E F G H

Page 21: Grafuri  orientate

• Procedând la fel pentru toate nodurile nemarcate, obţinem următorul rezultat:

91

4

9

3

1

25

14

1 2

A

B

C

D

EF

G

H

5

- 7 1 3 3 4 5 ∞

A B C D E F G H

A E A A C E F A

D:

T:

Din nodul F a fost descoperit acest drum nou (mai scurt) catre G

Page 22: Grafuri  orientate

91

4

9

3

1

25

14

1 2

A

B

C

D

EF

G

H

5

- 7 1 3 3 4 5 ∞

A B C D E F G H

D:

Nu exista drumuri mai scurte spre B sau H trecand prin G, deci

tablourile D si T raman nemodificate

• Se alege nodul G şi se marchează, deoarece nodul G are intrarea în tabloul D minimă – drumul minim de la A la G are lungimea 5 (nu vom găsi altul mai scurt până la final).

Page 23: Grafuri  orientate

• Se alege nodul B şi se marchează, deoarece nodul B are intrarea in tabloul D minima– drumul minim de la A la B are lungimea 7 (nu vom gasi altul mai scurt pana la final)

91

4

9

3

1

25

14

1 2

A

B

C

D

EF

G

H

5

- 7 1 3 3 4 5 ∞

A B C D E F G H

D:

Nu există drum mai scurt spre H trecând

prin B, deci tablourile D si T rămân nemodificate

Page 24: Grafuri  orientate

• Se alege nodul H si se marchează, deoarece nodul H are intrarea în tabloul D minima – drumul minim de la A la H are lungimea ∞ (adică nu există), caz în care punem T[H] = ‘–’.

91

4

9

3

1

25

14

1 2

A

B

C

D

EF

G

H

5

- 7 1 3 3 4 5 ∞

A B C D E F G H

D:

Nu mai există noduri nemarcate care sa fie

actualizate, deci tablourile D si T raman

nemodificate

Page 25: Grafuri  orientate

• Algoritmul se încheie deoarece nu mai sunt noduri nemarcate• Rezultatul este:

• Lungimile drumurilor minime de la A la celelalte noduri din graf sunt disponibile in tabloul D.

• Tabloul T serveşte la reconstituirea drumurilor.

• Putem reconstitui drumurile in două moduri:– intuitiv, urmărind arcele îngroşate de pe graf (de exemplu, drumul minim de la A la G

este A -> C -> E -> F -> G).– formal, utilizând tabloul T rezultat în urma aplicării algoritmului.

- 7 1 3 3 4 5 ∞

A B C D E F G H

A E A A C E F -

D:

T:

91

4

9

3

1

25

14

1 2

A

B

C

D

EF

G

H

5

Page 26: Grafuri  orientate

• Tabloul T este:

• Dacă consideram că acest tablou reprezintă un arbore generalizat în implementarea cu indicatori spre părinte, atunci drumul minim de la A la G poate fi reconstituit pornind de la G:

• T[G] = F• T[F] = E• T[E] = C• T[C] = A

• Mergând invers, obtinem: A -> C -> E -> F -> G.• Arborele generalizat obţinut în tabloul T conţine toate drumurile

minime cu originea în A.

• Algoritmul găseşte doar drumuri minime cu originea într-un anumit nod al grafului.

• Dacă se doresc drumuri minime cu originea în alt nod, trebuie repornit algoritmul cu respectivul nod pe post de nod de start.

• Drumurile minime obţinute pot fi reprezentate ca un arbore generalizat, deoarece ele se suprapun în mare parte.

• Astfel, dacă drumul minim de la X la Y trece prin Z, el trebuie obligatoriu să cuprindă si drumul minim de la X la Z.

A E A A C E F -

A B C D E F G H

Page 27: Grafuri  orientate

După ce a înţeles cum funcţiona acest algoritm, Alin,le-a spus şi

celorlalţi doi despre ideea lui,iar aceştia s-au oferit să îi dea o mână de ajutor in realizarea programului.

Cei trei, au considerat fiecare nod al grafului ca fiind câte o staţie TAXI, arcele reprezentând străzile din oraş, iar costurile erau reprezentate de distanţa dintre noduri. Şi uite aşa ei au reuşit să mulţumească clienţii şi profitu lor să fie mult mai prosper.

Întotdeauna ceea ce vei învăţa la şcoală, te va ajuta şi-n viaţa de zi cu zi.

Învaţă şi vei fi pe DRUMUL cel bun!

Page 28: Grafuri  orientate

#include <iostream>#include <fstream>int a[20][20],d[20],viz[20],n,m,start;void citire (){ int i,x,y,c; ifstream fin ("graf.in"); fin>>n>>m>>start; for (i=1;i<=m;i++){ fin>>x>>y>>c; a[x][y]=c; }}void drum_minim (){ int i,j,minim,nodminim; viz[start]=1; for (i=1;i<=n;i++){ if (a[start][i]) d[i]=a[start][i]; else d[i]=99999; }

d[start]=0; for (i=1;i<=n;i++){ minim=99999; for (j=1;j<=n;j++){ if (!viz[j] && d[j]<minim){ minim=d[j]; nodminim=j; } } viz[nodminim]=1; for (j=1;j<=n;j++){ if (a[nodminim][j] && d[j]>minim+a[nodminim][j]) d[j]=minim+a[nodminim][j]; } }}int main (){ int i; citire (); drum_minim (); for (i=1;i<=n;i++){ cout<<"Distanta minima dintre "<<start<<" si "<<i; cout<<" este "<<d[i]<<'\n'; } return 0;}