Algoritmul lui Dijkstra pentru Calculul Tuturor Drumurilor de Cost Minim

Prezentarea algoritmului standard

Algoritmul Dijkstra este un algoritm care calculeaza drumurile minime de la un nod al unui graf la toate celelalte noduri din graf . Grafurile pe care poate lucra algoritmul lui Dijkstra sunt, in general, ponderate si orientate – arcele sunt orientate de la un nod la alt nod (nu se poate merge si invers) si au un anumit cost de care se va 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 . Pentru a gasi drumul minim de la un nod X la un nod Y se poate aplica o cautare prin cuprindere pornind de la nodul X – prima aparitie a lui Y in coada algoritmului de cautare prin cuprindere presupune existenta unui drum cu numar minim de arce de la X la Y, care poate fi reconstituit . Pe un astfel de graf se poate aplica si algoritmul lui Dijkstra, daca transformam in prealabil graful intr-unul ponderat, asociind fiecarui arc acelasi cost (de exemplu, costul 1). Drumul de cost minim intre doua noduri obtinut in urma aplicarii algoritmului lui Dijkstra va avea si numar minim de arce din moment ce toate arcele au acelasi cost.

Algoritmul lui Dijkstra functioneaza atat pe grafuri conexe cat si pe grafuri neconexe. Un graf este conex daca din orice nod al sau se poate ajunge in orice alt nod. In cazul grafurilor orientate, pentru ca intre doua noduri sa existe un drum in graf, nu este suficient sa existe o succesiune de arce intre cele doua noduri, ci arcele trebuie sa fie si orientate in sensul corespunzator . Un drum intr-un graf orientat trebuie sa parcurga numai arce orientate identic, de la nodul sursa pana la nodul destinatie . Daca nu exista nici un drum de la nodul de start la un alt nod al grafului atunci algoritmul lui Dijkstra va raporta existenta unui drum de lungime infinita intre ele – acest rezultat indica, de fapt, lipsa oricarui drum intre cele doua noduri .

Intrare:

• Algoritmul porneste de la un graf orientat si ponderat cu N noduri

• De asemenea, e nevoie de un nod de start apartinand grafului – acesta este nodul de la care se doreste aflarea drumurilor minime pana la celelalte noduri din graf

Iesire:

• Rezultatul algoritmului se prezinta sub forma unui tablou D cu N intrari, continand distantele minime de la nodul de start la toate celelalte noduri din graf

• De asemenea, tot ca rezultat se poate obtine si arborele drumurilor minime (in cazul in care ne intereseaza nu numai lungimile minime ale drumurilor, ci si drumurile propriu-zise) – acesta este un arbore generalizat care se va obtine sub forma unui tablou T cu N intrari (implementarea cu indicatori spre parinte)

Fie X nodul de start – acesta se marcheaza ca vizitat . Ideea gasirii drumului minim de la X la un un alt nod este cautarea treptata: se presupune ca drumul minim este alcatuit dintr-un singur arc (arcul direct intre X si nodul tinta, care poate sa nu existe, costul sau fiind infinit in acest caz), apoi se cauta drumuri mai scurte alcatuite 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).

Dupa pasul k (1 ≤ k ≤ N-1), tabloul D va contine lungimile drumurilor minime de la nodul X la celelalte noduri, toate aceste drumuri fiind alcatuite din maxim k arce .

Astfel, D[Y] = L dupa pasul k inseamna ca de la X la Y exista un drum minim de lungime L alcatuit din maxim k arce . Deci, dupa pasul k, au fost gasite numai drumurile minime alcatuite din maxim k arce – abia la finalul algoritmului (dupa pasul N-1) drumurile minime obtinute sunt definitive, ele fiind drumuri minime alcatuite din maxim N-1 arce . La inceputul fiecarui pas k avem un set de k-1 noduri marcate (in cadrul pasilor precedenti) – nodurile marcate sunt cele pentru care se cunoaste drumul minim (initial, doar nodul de start este marcat deoarece doar pentru el se cunoaste drumul minim).