7/22/2019 16. Algoritmul Lui Dijkstra

1/3

16. Algoritmul lui Dijkstra

Este destinat aflrii celor mai scurte ci de la un nod dat la toate

celelalte noduri ale grafului;

Se creeaz astfel un arbore de acoperire, care are ca rdcin nodul

iniial dat !numit "i surs#, iar fiecare ramur reprezint cea mai scurt

cale de la surs la toate nodurile pe care le conine.

Acest arbore, $n general, difer de arborele de cost minim.

%entru aplicarea acestui algoritm, se folosesc dou structuri de date

au&iliare'

( Arborele S, care conine cile cele mai scurte ctre noduri; iniial,

acest arbore conine numai nodul surs, dar el se completeaz cu un

nou nod la fiecare parcurgere a ciclului )reed*;

( coada de prioriti +, care conine nodurile care nu sunt $n S, dar

ctre care conduc legturi de la nodurile din S; la e&tragerea din coad,

prioritatea ma&im aparine nodului pentru care distana de la surs

este cea mai mic.

niial, se creeaz structurile -ide S "i +, dup care se pune nodul surs

$n +.

iecrui nod din + i se ata"eaz ca informaie distana de la nodul surs

p/n la nodul dat.

Se intr apoi $ntr(un ciclu )reed*.

0a fiecare parcurgere a ciclului se e&trage din + nodul de prioritate

ma&im !deci cel pentru care distana de la nodul sursa este minim# "i

se pune $n S.

%entru a se putea reconstitui arborele, $n structurile S "i + fiecare

element -a conine "i o referin la tatl acestuia, deci -a fi reprezentat

prin urmtorul triplet'

!tata2 nod3curent2 distan3la3surs2#

7/22/2019 16. Algoritmul Lui Dijkstra

2/3

Este un algoritm care calculeaza drumurile minime de la un nod al unui

graf la toate celelalte noduri din graf.

)rafurile pe care poate lucra algoritmul lui Dijkstra sunt, in general,

ponderate si orientate 4 arcele sunt orientate de la un nod la alt nod !nuse poate merge si in-ers# si au un anumit cost de care se -a tine seama in

aflarea drumului minim.

Daca graful este neponderat !arcele nu au costuri asociate# atunci drum

minim intre doua noduri se considera drumul alcatuit din numar minim

de arce.

%entru a gasi drumul minim de la un nod 5 la un nod se poate aplica

o cautare prin cuprindere pornind de la nodul 5 4 prima aparitie a lui in coada algoritmului de cautare prin cuprindere presupune e&istenta

unui drum cu numar minim de arce de la 5 la , care poate fi

reconstituit.

%e un astfel de graf se poate aplica si algoritmul lui Dijkstra, daca

transformam in prealabil graful intr(unul ponderat, asociind fiecarui

arc acelasi cost.

Drumul de cost minim intre doua noduri obtinut in urma aplicariialgoritmului lui Dijkstra -a a-ea si numar minim de arce din moment

ce toate arcele au acelasi cost.

Algoritmul lui Dijkstra functioneaza atat pe grafuri cone&e cat si pe

grafuri necone&e.

7n graf este cone& daca din orice nod al sau se poate ajunge in orice alt

nod.

n cazul grafurilor orientate, pentru ca intre doua noduri sa e&iste un

drum in graf, nu este suficient sa e&iste o succesiune de arce intre cele

doua noduri, ci arcele trebuie sa fie si orientate in sensul corespunzator.

7n drum intr(un graf orientat trebuie sa parcurga numai arce orientate

identic, de la nodul sursa pana la nodul destinatie.

7/22/2019 16. Algoritmul Lui Dijkstra

3/3

Daca nu e&ista nici un drum de la nodul de start la un alt nod al grafului

atunci algoritmul lui Dijkstra -a raporta e&istenta unui drum de

lungime infinita intre ele 4 acest rezultat indica, de fapt, lipsa oricarui

drum intre cele doua noduri

ntrare'

Algoritmul porneste de la un graf orientat si ponderat cu 8

noduri;

De asemenea, e ne-oie de un nod de start apartinand grafului 4

acesta este nodul de la care se doreste aflarea drumurilor minime

pana la celelalte noduri din graf.

esire'

9ezultatul algoritmului se prezinta sub forma unui tablou D cu 8

intrari, continand distantele minime de la nodul de start la toate

celelalte noduri din graf.