Creeaza.com - informatii profesionale despre


Cunostinta va deschide lumea intelepciunii - Referate profesionale unice
Acasa » scoala » informatica
Algoritmul Dijkstra pentru gasirea celui mai scurt traseu intre doua noduri date ale unui graf

Algoritmul Dijkstra pentru gasirea celui mai scurt traseu intre doua noduri date ale unui graf


Algoritmul Dijkstra pentru gasirea celui mai scurt traseu intre doua noduri date ale unui graf

Multi algoritmi care opereaza asupra grafurilor implica o etichetare a nodurilor sau ramurilor in conformitate cu o anumita regula. Etichetele pot reprezenta distantele de la un anumit nod, capacitatea liniei respective etc.

Vom ilustra posibilitatea etichetarii printr-un algoritm (elaborat de Djikstra in 1959) care se utilizeaza pentru gasirea celei mai scurte cai intre doua noduri specificate ale grafului respectiv.

Fiecarui nod i se ataseaza o eticheta - intre paranteze - ce contine distanta fata de un nod sursa, de-a lungul caii celei mai scurte. Algoritmul este urmatorul:



Initial, nici o cale nu este cunoscuta, deci toate nodurile sunt etichetate cu valoarea infinit (fara specificarea nodului sursa). Pe masura ce algoritmul se desfasoara si se gasesc caile etichetele se pot schimba reflectand o cale mai buna. Asadar o eticheta poate fi temporara (tentativa) sau permanenta. Initial, toate etichetele sunt tentative. Atunci cand se descopera ca o eticheta reprezinta cea mai scurta cale de la o sursa la un nod, ea devine permanenta.

Vom exemplifica algoritmul de etichetare pe un graf orientat ponderat, in care ponderea semnifica distanta, in scopul gasirii celei mai scurte cai de la nodul A la nodul D.

Pasul Se incepe cu nodul A, marcandu-l ca nod permanent, prin punct plin. Se examineaza apoi, pe rand fiecare dintre nodurile adiacente lui A (nodul asupra caruia se lucreaza se marcheaza cu o sageata) reetichetandu-l cu distanta de la A la el. ori de cate ori se reeticheteaza un nod, in eticheta se inscrie nodul fata de care se face proba, fapt ce permite sa se reconstituie mai tarziu calea finala. Dupa ce au fost examinate toate nodurile adiacente lui A se compara etichetele acestora si se ia drept eticheta permanenta cea a nodului cu cea mai mica valoarea - nodul B in cazul din exemplu - marcand respectivul nod prin punct plin. Toate celelalte noduri neabordate din graf se marcheaza cu etichete tentative (infinit).

Pornind acum din nodul B (marcat cu o sageata la pasul 1) se vor examina la pasul 2 nodurile adiacente lui si care nu au etichete permanente (C si E), calculandu-le distanta fata de A, ca suma a distantei de la A la B plus distanta de la B la nodul respectiv. Daca suma este mai mica decat valoarea distantei inscrisa in eticheta anterioara acelui nod, nodul se va reeticheta cu aceasta suma si cu numele nodului adiacent anterior prin care s-a obtinut aceasta cale mai scurta de la A pana la nodul examinat (asa cum s-a procedat pentru ambele noduri testate, C si E). Se compara apoi, tot la pasul 2, toate etichetele tentativa din graf si se ia drept nod permanent cel cu cea mai mica distanta din eticheta (marcandu-l prin punct plin) - in cazul de fata nodul E - el devenind noul nod de lucru (il vom marca cu o sageata).

D

 

D

 

Pasul 4

 

Pasul 5

 

Nod cu eticheta tentativa

  Nod cu eticheta permanenta

  Nod asupra caruia se lucreaza

 


Observatie

Pentru a dovedi justetea algoritmului, sa presupunem ca ABE nu este cea mai scurta cale, deci ar exista o alta, fie ea AXYZE. Atunci exista doua posibilitati:

Z a fost facut nod permanent la pasul anterior si atunci ea a fost probata la pasul imediat urmator permanentizarii lui Z, ceea ce ar fi facut imposibila pierderea din vedere a caii AXYZE;

Z este un nod cu eticheta tentativa si atunci apar doua cazuri:

distanta totala din eticheta lui Z este mai mare sau egala cu cea din eticheta lui E, caz in care AXYZE nu poate fi mai scurta decat ABE;

distanta totala din eticheta lui Z este mai mica decat cea din eticheta lui E, in care caz Z si nu E ar fi devenit permanent mai intai, permitand examinarea lui E pornind de la Z

La pasul 3, pornind de la nodul de lucru E, se testeaza nodurile adiacente (F si G) reetichetandu-se ambele (deoarece distanta reetichetandu-se ambele (deoarece distanta totala pe calea ABEG are o valoare 5, mai mic decat 6 - valoarea distantei din vechea eticheta a nodului G). Comparand toate etichetele tentativa din graf, descoperim ca nodul G are cea mai mica valoare si deci pe el il vom face permanent, devenind viitorul nod de lucru.

La pasul 4 vom avea de examinat doar nodul H, singurul adiacent lui G si avand o eticheta tentativa. Dupa reetichetarea sa, din analiza tuturor nodurilor tentativa din graf constatam ca F are in eticheta cea mai mica distanta, il luam drept nod permanent si totodata nod de lucru pentru urmatorul pas.

La pasul 5 se vor analiza nodurile C si H. Se constata ca la nodul H este necesara o reetichetare, dar la C nu este cazul deoarece distanta insumata pe calea ABEFC este egala cu cea din vechea eticheta (9 pe calea AABC). Din compararea etichetelor tentativa ale intregului graf se constata ca la nodul H este cea mai mica valoare a distantei in eticheta si, ca atare, el va fi permanentizat si va fi adoptat drept nod de lucru nou.

La pasul 6 se reeticheteaza nodul D cu eticheta (10,H) si permanentizarea sa.

A rezultat calea ABEFHD ca fiind cea mai scurta (distanta totala de la A la D este egala cu 10).





Politica de confidentialitate


creeaza logo.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Comentarii literare

ALEXANDRU LAPUSNEANUL COMENTARIUL NUVELEI
Amintiri din copilarie de Ion Creanga comentariu
Baltagul - Mihail Sadoveanu - comentariu
BASMUL POPULAR PRASLEA CEL VOINIC SI MERELE DE AUR - comentariu

Personaje din literatura

Baltagul caracterizarea personajelor
Caracterizare Alexandru Lapusneanul
Caracterizarea lui Gavilescu
Caracterizarea personajelor negative din basmul

Tehnica si mecanica

Cuplaje - definitii. notatii. exemple. repere istorice.
Actionare macara
Reprezentarea si cotarea filetelor

Economie

Criza financiara forteaza grupurile din industria siderurgica sa-si reduca productia si sa amane investitii
Metode de evaluare bazate pe venituri (metode de evaluare financiare)
Indicatori Macroeconomici

Geografie

Turismul pe terra
Vulcanii Și mediul
Padurile pe terra si industrializarea lemnului

Lucrare de atestare profesionala INFORMATICA
Informatica - ce este informatica?
Caracteristicile celor patru tipuri de sisteme informationale
Sumatoare seriale
CALCULUL CLIENT/SERVER
Microcontrolerul AT89C52
UTILIZAREA CONCEPTELOR SPECIFICE ORGANIZATIILOR VIRTUALE IN PRACTICA MEDICALA DIN ROMANIA
MICROSOFT WORD

Termeni si conditii
Contact
Creeaza si tu