Algoritmul lui Dijkstra
Algoritmul lui Dijkstra | |
---|---|
Executarea algoritmului lui Dijkstra | |
Clasă | Algoritm de căutare |
Structură de date | Grafic |
Cel mai rău caz din punct de vedere temporal | [1] |
Algoritmul lui Dijkstra este un algoritm folosit pentru a căuta cele mai scurte căi într-un grafic cu sau fără ordonare, ciclic și cu greutăți non-negative pe margini. A fost inventat în 1956 de informaticianul olandez Edsger Dijkstra care l-a publicat mai târziu în 1959. Acest algoritm își găsește aplicația în multe contexte precum optimizarea în construcția de rețele (apă, telecomunicații , drumuri, circuite etc.) sau organizarea și evaluarea a căilor de rulare în domeniul roboticii .
Algoritm
Să presupunem că avem un grafic cu n vârfuri marcate cu numere întregi {1,2, ..., n} și că unul dintre aceste noduri este cel de pornire și altul cel de destinație. Greutatea pe arc care unește nodurile j și k este indicată de p (j, k) . La sfârșitul analizei, fiecare nod trebuie să fie asociat cu două etichete, f (i) care indică greutatea totală a căii (suma greutăților pe arcurile parcurse pentru a ajunge la nodul i) și J (i ) care indică nodul care precede i în cea mai scurtă cale. Mai mult, definim două seturi S și T care conțin respectiv nodurile cărora etichetele le-au fost deja atribuite și cele care urmează să fie scanate.
- Inițializare .
- Să setăm S = {1}, T = {2,3, ..., n}, f (1) = 0, J (1) = 0.
- Setăm f (i) = p (1, i), J (i) = 1 pentru toate nodurile adiacente la 1.
- Setăm f (i) = ∞, pentru toate celelalte noduri.
- Alocarea permanentă a etichetelor
- Dacă f (i) = ∞ pentru fiecare i din T STOP
- Găsim j în T astfel încât f (j) = min f (i) cu i aparținând lui T
- Să setăm T = T {j} și S = S∪ {j}
- Dacă T = Ø STOP
- Alocarea temporară a etichetei
- Pentru tot i în T, adiacent j astfel încât f (i)> f (j) + p (j, i) stabilim:
- f (i) = f (j) + p (j, i)
- J (i) = j
- Să trecem la pasul 2
- Pentru tot i în T, adiacent j astfel încât f (i)> f (j) + p (j, i) stabilim:
Pseudo cod
În următorul algoritm, codul u := vertici in Q con la più breve dist[]
, caută noduri u
în setul de noduri Q
care au cea mai mică valoare dist[ u ]
. Aceste noduri sunt eliminate din setul Q
și returnate utilizatorului. dist_between( u , v )
calculează distanța dintre două noduri vecine u
și v
. Variabila alt
din liniile 20 22 reprezintă lungimea căii de la nodul de pornire la nodul vecin v
dacă trece prin u
. Dacă această cale este mai scurtă decât ultima cale înregistrată pentru v
, atunci calea curentă este înlocuită de calea identificată cu alt
. Matricea precedente
este populată cu un indicator către următorul nod al graficului sursă pentru a primi cea mai scurtă cale de la sursă.
1 funcție Dijkstra ( grafic , sursă ): 2 Pentru fiecare vârf v din Grafic : // Inițializare 3 dist [ v ]: = infinit; // Distanța inițială necunoscută 4 // din sursa av 5 precedent [ v ]: = nedefinit; // Nodul anterior într-o cale optimă 6 capăt pentru // de la sursă 7 8 dist [ sursa ]: = 0; // Distanța de la sursă la sursă 9 Î : = Setul tuturor nodurilor din grafic ; // Toate nodurile din grafic sunt 10 // Nu este optimizat și, prin urmare, se încadrează în Q 11 în timp ce Q nu este gol: // Bucla principală 12 u : = vârf în Q cu cea mai mică distanță în dist []; // Nod de pornire pentru primul caz 13 scoate u din Q; 14 dacă dist [ u ] = infinit: 15 pauză ; // toate vârfurile rămase sunt 16 end if // inaccesibil de la nodul sursă 17 18 Pentru fiecare vecin v de u : 20 alt : = dist [ u ] + dist_tra ( u , v ); 21 dacă alt <dist [ v ]: // această condiție este întotdeauna falsă dacă a fost deja eliminată din Q 22 dist [ v ]: = alt ; 23 precedent [ v ]: = u ; 24 tasta de scădere v în Q ; // Reordonați v în coadă 25 sfârșit dacă 26 final pentru 27 se termină în timp ce 28 întoarcere dist;
Dacă ne interesează doar calea cea mai scurtă dintre două noduri sorgente
și destinazione
, putem încheia căutarea pe linia 13 dacă u = destinazione
. Acum putem citi cea mai scurtă cale de la sorgente
la destinazione
printr-o iterație inversă:
1 S : = secvență goală 2 u : = destinație 3 în timp ce [ u ] anterior este definit: // Construiți cea mai scurtă cale cu o stivă S 4 introduceți u la începutul lui S // Împingeți vârful pe teanc 5 u : = precedent [ u ] // Treceți de la destinație la sursă. 6 sfârșesc în timp ce ;
Acum secvența S
este lista nodurilor care alcătuiesc o cale mai scurtă de la sorgente
la destinazione
sau secvența goală dacă nu există căi mai scurte existente.
Timpul de execuție
Complexitatea de calcul a algoritmului lui Dijkstra poate fi exprimată în funcție de și adică numărul de noduri și arce aparținând graficului pe care este executat. Algoritmul folosește o coadă prioritară pe care se efectuează trei operații: construirea cozii, extragerea elementului minim și reducerea valorii unui element. Structura de date utilizată pentru implementarea cozii prioritare determină complexitatea acestor trei operații și, în consecință, cea a algoritmului.
În general, complexitatea, , a algoritmului lui Dijkstra este delimitată mai sus de
unde este , Și sunt complexitățile necesare operațiunilor de construcție ale unei cozi cu elemente, extragerea minimului dintr-o coadă cu elemente și reducerea unei valori într-o coadă cu elemente.
Complexitatea , , și algoritmul lui Dijkstra în cazul în care cozile prioritare sunt implementate prin matrice, heap binar sau heap Fibonacci .
Construind coada | Extrageți minimul | Reduceți o valoare | Algoritmul lui Dijkstra | |
---|---|---|---|---|
Matrice | ||||
Heap binar | ||||
Heap Fibonacci | [2] | [2] | [2] |
Este interesant de observat că, în cazul în care graficul nu este suficient de rar și , soluția bazată pe matrice este mai eficientă decât cea implementată prin grămezi binare .
Exemplu
La baza acestor probleme se află scopul de a găsi cea mai scurtă cale (cea mai scurtă, cea mai rapidă, cea mai ieftină ...) între două puncte, unul de plecare și unul de sosire. Cu metoda care va fi văzută, este posibil să se obțină nu numai calea minimă dintre un punct de plecare și un punct de sosire, ci arborele celor mai scurte căi , adică toate căile minime dintre un punct de plecare și toate celelalte puncte ale rețeaua. Ca și în cazul tuturor problemelor legate de rețele, cel mai bun lucru este să faceți o schemă a situației pentru a rezolva mai ușor exercițiul și pentru a avea întotdeauna la dispoziție datele necesare. O bună schematizare pentru problemele minime de cale trebuie să includă toate legăturile posibile între noduri (și costurile acestora) și un nod de pornire trebuie stabilit.
Luați în considerare o problemă în care doriți să calculați cea mai mică distanță dintre casă și serviciu. Sunt prezentate toate rutele posibile și timpul relativ de călătorie (presupunând că doriți să calculați cea mai scurtă rută din punct de vedere al timpului de călătorie). Nodurile A, B, C, D, E indică orașele prin care este posibil să treacă. Iată o schemă a rețelei:
Acum este necesar să atribuiți fiecărui nod o valoare, numită „potențial”, urmând câteva reguli:
- Fiecare nod are potențial la început (pe care îl indicăm cu „inf”);
- Nodul de pornire (în acest caz „casă”) are potențialul 0 (adică este zero de la sine);
- De fiecare dată când nodul cu cel mai mic potențial este ales și definit (prin colorarea potențialului în roșu) și nodurile adiacente sunt actualizate;
- Potențialul unui nod este dat de suma potențialului nodului anterior + costul legăturii;
- Potențialele nodurilor definite nu sunt actualizate;
- Potențialele finale indică distanța acelui nod de cel inițial;
- Când actualizați potențialul unui nod, îl lăsați pe cel mai mic (fiind o problemă minimă de cale).
Vedeți cum se rezolvă acest exercițiu în practică. Aceasta este rețeaua în care sunt indicate și potențialele:
Urmând regulile abia stabilite, luați în considerare nodul cu cel mai mic potențial („casă”) și faceți-l definitiv (colorându-l în roșu) și actualizați toate nodurile adiacente adăugând valoarea curentă a potențialului (adică zero) la costul cale. Actualizăm potențialele pentru că am avut, în cazul lui A, potențial infinit în timp ce acum potențialul este 2. Amintindu-ne că potențialul mai mic este întotdeauna preferabil. Iată cum s-a actualizat rețeaua:
Acum este necesar să se ia în considerare nodul nedefinitiv (adică cele scrise în negru) cu cel mai mic potențial (nodul A). Faceți-l definitiv și actualizați potențialele nodurilor adiacente B și C. Indicați cu o săgeată de unde vine potențialul nodurilor definite.
Nodul cu cel mai mic potențial este acum C. faceți-l definitiv și actualizați-le pe cele adiacente.
Trebuie remarcat faptul că nodul D are acum potențialul 6, deoarece 6 este mai mic decât 8 și, prin urmare, este actualizat. Dacă ați fi obținut o valoare mai mare decât ceea ce era deja acolo, ar fi trebuit să fie lăsată neschimbată. Faceți nodul D definitiv și actualizați graficul:
Nodul cu potențialul minor rămas este B și se face definitiv prin actualizarea graficului în consecință:
Nodul E rămâne de luat în considerare și „biroul” de actualizat.
Urmând săgețile înapoi veți obține calea minimă de acasă la birou care măsoară (așa cum este indicat de potențial) „10”.
Trebuie remarcat faptul că acest algoritm ne oferă nu numai distanța minimă dintre punctul de plecare și punctul de sosire, ci distanța minimă a tuturor nodurilor de la punctul de plecare, din care se poate crea cel mai scurt arbore de cale, eliminând doar arcurile utilizate. pe nici o cale.
Notă
Bibliografie
- Michael T. Goodrich, Roberto Tamassia, Structuri de date și algoritmi în Java , Bologna, Zanichelli Editore, 2007, pp. 556-561, ISBN 978-88-08-07037-1 .
Elemente conexe
- Algoritmul Bellman-Ford
- Algoritmul lui Prim
- Algoritmul lui Kruskal
- Algoritmul Floyd-Warshall
- PERT / CPM
- Aprofundarea iterativă
Alte proiecte
- Wikimedia Commons conține imagini sau alte fișiere pe algoritmul Dijkstra