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
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 |
 .com |
Copyright ©
2024 - Toate drepturile rezervate. Toate documentele au caracter informativ cu scop educational. |
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 |
Geografie |
| Turismul pe terra |
| Vulcanii Și mediul |
| Padurile pe terra si industrializarea lemnului |
| Termeni si conditii |
| Contact |
| Creeaza si tu |
