Algoritmul lui Dijkstra

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Notă despre dezambiguizare.svg Dezambiguizare - Dacă sunteți în căutarea algoritmului de excludere reciprocă în sistemele concurente, numit și „algoritmul de proiecție Dijkstra”, consultați intrarea algoritmului Dekker .
Algoritmul lui Dijkstra
Dijkstra Animation.gif
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.

  1. 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.
  2. 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
  3. 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

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 .

Complexitatea algoritmului Dijkstra în funcție de implementarea cozii prioritare
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:

Căi minime de cercetare operațională 01.gif

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:

Căi minime de cercetare operațională 02.gif

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:

Căi minime de cercetare operațională 03.gif

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.

Căi minime de cercetare operațională 04.gif

Nodul cu cel mai mic potențial este acum C. faceți-l definitiv și actualizați-le pe cele adiacente.

Calea minimă de cercetare operațională 05.gif

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:

Căi minime de cercetare operațională 06.gif

Nodul cu potențialul minor rămas este B și se face definitiv prin actualizarea graficului în consecință:

Căi minime de cercetare operațională 07.gif

Nodul E rămâne de luat în considerare și „biroul” de actualizat.

Căi minime de cercetare operațională 08.gif

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”.

Căi minime de cercetare operațională 09.gif

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

Alte proiecte