Algoritmul lui Dijkstra

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 23 februarie 2022; verificările necesită 8 modificări .

Algoritmul lui Dijkstra este un algoritm grafic inventat de savantul olandez Edsger Dijkstra în 1959 . Găsește cele mai scurte căi de la unul dintre vârfurile graficului la toate celelalte. Algoritmul funcționează numai pentru grafice fără muchii cu greutate negativă . Algoritmul este utilizat pe scară largă în programare, de exemplu, este utilizat de protocoalele de rutare OSPF și IS-IS .

Declarația problemei

Exemple

Opțiunea 1. Având în vedere o rețea de drumuri care leagă orașele din regiunea Moscovei. Unele drumuri sunt cu sens unic. Găsiți cele mai scurte căi de la orașul A la fiecare oraș din regiune (dacă vă puteți deplasa doar pe drumuri).

Opțiunea 2. Există o serie de zboruri între orașele lumii, costul fiind cunoscut pentru fiecare. Costul unui zbor de la A la B poate să nu fie egal cu costul unui zbor de la B la A. Găsiți ruta cu cost minim (eventual cu transferuri) de la Copenhaga la Barnaul .

Definiție formală

Dat un grafic ponderat direcționat [1] fără arce de greutate negativă [2] . Găsiți cele mai scurte căi de la un vârf al graficului la toate celelalte vârfuri ale acestui grafic. $G(V,E)$ $A$ $G$

Explicație informală

Fiecărui vârf de la V i se atribuie o etichetă — distanța minimă cunoscută de la acest vârf la un .

Algoritmul funcționează pas cu pas - la fiecare pas „vizitează” un vârf și încearcă să reducă etichetele.

Algoritmul se termină când toate nodurile au fost vizitate.

Inițializare .

Eticheta vârfului a însuși se presupune a fi 0, etichetele celorlalte vârfuri sunt setate la infinit.

Acest lucru reflectă faptul că distanțele de la a la alte vârfuri nu sunt încă cunoscute.

Toate vârfurile graficului sunt marcate ca nevizitate.

Pasul algoritmului .

Dacă toate nodurile au fost vizitate, algoritmul se termină.

În caz contrar, din nodurile care nu au fost încă vizitate, este selectat vârful u cu eticheta minimă.

Luăm în considerare toate rutele posibile în care u este penultimul punct. Vârfurile la care duc muchiile de la u se numesc vecine acestui vârf. Pentru fiecare vecin al lui u , cu excepția celor marcate ca vizitate, luați în considerare o nouă lungime de cale egală cu suma valorilor etichetei curente u și lungimea muchiei care leagă u cu acest vecin.

Dacă valoarea lungimii primite este mai mică decât valoarea etichetei vecinului, înlocuiți valoarea etichetei cu valoarea lungimii obținute. Luând în considerare toți vecinii, marchem vârful u ca vizitat și repetăm pasul algoritmului .

Exemplu

Luați în considerare execuția algoritmului pe exemplul graficului prezentat în figură.

Să fie necesar să se găsească cele mai scurte distanțe de la primul vârf la toate celelalte.

Cercurile indică vârfurile, liniile indică căile dintre ele (marginile graficului).

Numărul de vârfuri este indicat în cercuri, greutatea lor este indicată deasupra marginilor - lungimea căii.

Lângă fiecare vârf, este marcată o etichetă roșie - lungimea celei mai scurte căi către acest vârf de la vârful 1.

Primul pas .

Vârful 1 are eticheta minimă. Vârfurile 2, 3 și 6 sunt vecine.

Primul vecin al vârfului 1, la rândul său, este vârful 2, deoarece lungimea căii către acesta este minimă.

Lungimea căii către acesta prin vârful 1 este egală cu suma valorii etichetei vârfului 1 și lungimea muchiei care merge de la 1 la 2, adică 0 + 7 = 7.

Aceasta este mai mică decât eticheta curentă a vârfului 2, infinit, deci noua etichetă a celui de-al doilea vârf este 7.

Efectuăm o operație similară cu alți doi vecini ai primului vârf - al 3-lea și al 6-lea.

Toți vecinii nodului 1 sunt verificați.

Distanța minimă actuală până la vârful 1 este considerată finală și nu este supusă revizuirii.

Tăiați-o din grafic pentru a marca că acest vârf a fost vizitat.

Al doilea pas .

Din nou găsim „cel mai apropiat” dintre vârfurile nevizitate. Acesta este vârful 2 etichetat 7.

Din nou încercăm să reducem etichetele vecinilor vârfului selectat, încercând să trecem prin ele prin al 2-lea vârf. Vecinii vârfului 2 sunt vârfurile 1, 3 și 4.

Primul (în ordine) vecin al vârfului 2 este vârful 1. Dar acesta a fost deja vizitat, așa că nu facem nimic cu primul vârf.

Următorul vecin este vârful 3, deoarece are eticheta minimă.

Dacă mergeți la el prin 2, atunci lungimea unei astfel de căi va fi egală cu 17 (7 + 10 = 17). Dar eticheta curentă a celui de-al treilea vârf este 9, care este mai mică de 17, deci eticheta nu se schimbă.

Un alt vecin al vârfului 2 este vârful 4.

Dacă mergeți la el prin al 2-lea, atunci lungimea unei astfel de căi va fi egală cu suma celei mai scurte distanțe până la al 2-lea vârf și a distanței dintre vârfurile 2 și 4, adică 22 (7 + 15 = 22) .

Deoarece 22< , setăm eticheta vârfului 4 la 22. $\infty$

Toți vecinii vârfului 2 au fost vizualizați, înghețăm distanța până la acesta și îl marchem ca vizitat.

Al treilea pas .

Repetăm pasul algoritmului selectând vârful 3. După „procesarea” acestuia, obținem următoarele rezultate:

Următorii pași .

Repetăm pasul algoritmului pentru vârfurile rămase. Acestea vor fi vârfurile 6, 4 și, respectiv, 5.

Finalizarea executiei algoritmului .

Algoritmul se termină când toate nodurile au fost vizitate.

Rezultatul algoritmului este vizibil în ultima figură: cea mai scurtă cale de la vârful 1 la 2 este 7, la 3 este 9, la 4 este 20, la 5 este 20, la 6 este 11.

Dacă la un moment dat toate vârfurile nevizitate sunt marcate cu infinit, atunci aceasta înseamnă că aceste vârfuri nu pot fi atinse (adică, graficul nu este conectat ). Apoi algoritmul poate fi finalizat înainte de program.

Algoritm

Notație

$V$ este mulțimea vârfurilor graficului
$E$ este mulțimea muchiilor graficului
$cu[ij]$ - greutatea (lungimea) coastei $ij$
$A$ - vârful, distanţele de la care se caută
$U$ - set de vârfuri vizitate
$d[u]$ — la sfârșitul algoritmului este egală cu lungimea celui mai scurt drum de la sus $A$ $u$
$p[u]$ — la sfârșitul algoritmului conține calea cea mai scurtă de la la $A$ $u$
$v$ este vârful curent considerat de algoritm

Cod de implementare a algoritmului

Mai jos este codul pentru implementarea algoritmului în limbajul de programare Java . Această opțiune de implementare nu este cea mai bună, dar arată clar posibila implementare a algoritmului:

clasa Dijkstra { dublu [] dist = dublu nou [ GV () ] ; Edge [] pred = margine nouă [ GV () ] ; public Dijkstra ( WeightedDigraph G , int s ) { boolean [] marcat = boolean nou [ GV () ] ; pentru ( int v = 0 ; v < GV ( ); v ++ ) dist [ v ] = Dublu . POSITIVE_INFINITY ; MinPQplus < Double , Integer > pq ; pq = nou MinPQplus < Double , Integer > (); \\ Coada prioritară dist [ s ] = 0,0 ; pq . pune ( dist [ s ] , s ); în timp ce ( ! pq . este gol ()) { intv = pq . _ delmin (); dacă ( marcat [ v ] ) continuă ; marcat ( v ) = adevărat ; pentru ( Muchia e ( v )) { int w = e . la (); dacă ( dist [ w ]> dist [ v ] + e . greutate ()) { dist [ w ] = dist [ v ] + e . greutate (); pred [ w ] = e ; pq . insert ( dist [ w ] , w ); } } } } }

Pseudocod

Atribui

$d[a]\obține 0,\p[a]\obține 0$

Pentru toate altele decât , atribuim . $u\în V$ $A$ $d[u]\gets\infty$

la revedere . Fie un vârf cu minim $\există v\notin U$ $v\notin U$ $d[v]$ $v$ $U$

Pentru toți cei care $tu\notin U$ $vu\in E$

dacă atunci $d[u]>d[v]+w[vu]$

Schimbare $d[u]\gets d[v]+w[vu]$

Schimbare $p[u]\gets (p[v],u)$

Descriere

În cea mai simplă implementare, o matrice de numere poate fi folosită pentru a stoca numerele d [ i ], iar o matrice de variabile booleene poate fi folosită pentru a stoca apartenența unui element în mulțimea U.

La începutul algoritmului, se presupune că distanța pentru vârful inițial este zero și toate celelalte distanțe sunt umplute cu un număr pozitiv mare (mai mare decât calea maximă posibilă din grafic ). Tabloul flags este umplut cu zerouri. Apoi începe bucla principală.

La fiecare pas al buclei, căutăm un vârf cu o distanță minimă și un steag egal cu zero. Apoi setăm steagul la 1 și verificăm toate vârfurile adiacente acestuia . Dacă în ele (în ) distanța este mai mare decât suma distanței până la vârful curent și lungimea muchiei, atunci o reducem. Bucla se termină când steagurile tuturor nodurilor devin egale cu 1 sau când toate nodurile cu steag sunt 0 . Cel din urmă caz este posibil dacă și numai dacă graficul G este deconectat. $v$ $u$ $u$ $d[i]=\infty$

Dovada corectitudinii

Fie lungimea celei mai scurte căi de la vârf la vârf . Să demonstrăm prin inducție că în momentul vizitei oricărui vârf , egalitatea este valabilă . $l(v)$ $A$ $v$ $z$ $d(z)=l(z)$

Baza. Vârful este vizitat mai întâi . În acest moment . $A$ $d(a)=l(a)=0$

Etapa. Să presupunem că am ales un vârf de vizitat . Să demonstrăm că în acest moment . Pentru început, observăm că pentru orice vârf este întotdeauna valabil (algoritmul nu poate găsi o cale mai scurtă decât cea mai scurtă dintre toate cele existente). Să fie calea cea mai scurtă de la la . Vârful este pornit și nu este vizitat. Prin urmare, setul de vârfuri nevizitate nu este gol. Fie primul vârf nevizitat pe , și fie cel care îl precede (deci vizitat). Deoarece calea este cea mai scurtă, porțiunea care duce de la până la este și cea mai scurtă, deci . $z\neq a$ $d(z)=l(z)$ $v$ $d(v)\geq l(v)$ $P$ $A$ $z$ $z$ $P$ $P$ $y$ $P$ $X$ $P$ $A$ $X$ $y$ $l(y)=l(x)+w(xy)$

Prin ipoteza de inducție, în momentul vizitei vârfului , , prin urmare, vârful a primit apoi o etichetă nu mai mare decât . Prin urmare, . Dacă , atunci se dovedește etapa de inducție. În caz contrar, deoarece vârful este selectat în prezent și nu , eticheta este minimă printre cele nevizitate, adică . Combinând acest lucru cu , avem , ceea ce urma să fie demonstrat. $X$ $d(x)=l(x)$ $y$ $d(x)+w(xy)=l(x)+w(xy)=l(y)$ $d(y)=l(y)$ $z=y$ $z$ $y$ $z$ $d(z)\leq d(y)=l(y)\leq l(z)$ $d(z)\geq l(z)$ $d(z)=l(z)$

Deoarece algoritmul se termină atunci când toate nodurile au fost vizitate, în acel moment pentru toate nodurile. $d=l$

Complexitatea algoritmului

Complexitatea algoritmului lui Dijkstra depinde de modul în care este găsit vârful v , de modul în care este stocat setul de vârfuri nevizitate și de cum sunt actualizate etichetele. Notați cu n numărul de vârfuri și cu m numărul de muchii din graficul G .

În cel mai simplu caz, atunci când întregul set de vârfuri este căutat pentru a găsi vârful cu minimul d [ v ] și se folosește o matrice pentru a stoca valorile lui d , timpul de rulare al algoritmului este . Bucla principală este executată de aproximativ n ori, în fiecare dintre ele se cheltuiesc aproximativ n operații pentru găsirea minimului. Ciclul prin vecinii fiecărui vârf vizitat necesită un număr de operații proporțional cu numărul de muchii m (deoarece fiecare muchie apare exact de două ori în aceste cicluri și necesită un număr constant de operații). Astfel, timpul total de rulare al algoritmului este , dar, din moment ce , este . $O(n^{2})$ $O(n^{2}+m)$ $m\leq n(n-1)$ $O(n^{2})$

Pentru graficele rare (adică cele pentru care m este mult mai mic decât n²), vârfurile nevizitate pot fi stocate într-un heap binar , iar valorile d [ i ] pot fi folosite ca cheie, apoi timpul pentru a elimina un vârf din va deveni în timp ce timpul de modificare va crește la . Deoarece bucla este executată de aproximativ n ori, iar numărul de modificări ale etichetei nu este mai mare de m , timpul de rulare al unei astfel de implementări este . $\overline U$ $\log n$ $d[i]$ $\log n$ $O(n\log n+m\log n)$

Dacă folosim un heap Fibonacci pentru a stoca vârfuri nevizitate , pentru care ștergerea are loc în medie pentru , iar valoarea scade în medie pentru , atunci timpul de rulare al algoritmului va fi . Cu toate acestea, conform prelegerilor lui Alekseev și Talanov [3] : $O(\log n)$ $O(1)$ $O(n\log n+m)$

constantele ascunse în estimările de cost asimptotice sunt mari, iar utilizarea grămezilor Fibonacci este rareori adecvată: grămezile binare obișnuite ( d-ary ) sunt mai eficiente în practică.

Alternativele la acestea sunt grămada groase, grămada subțire și grămada Brodal , care au aceleași estimări asimptotice, dar constante mai mici [4] .

Vezi și

Link -uri

C. Anisimov. Cum să construiți cel mai scurt traseu între două puncte.
Implementarea celei mai simple versiuni a algoritmului Dijkstra pe e-maxx.ru
Implementarea unei variante a algoritmului lui Dijkstra pentru grafice rare la e-maxx.ru
Implementarea unei variante a algoritmului lui Dijkstra cu o euristică rădăcină
algoritmul lui Dijkstra. Cod de program în Python
Exemplu YouTube
Algoritmul lui Dijkstra - implementarea algoritmului în diferite limbi pe Rosetta Code .

Literatură

Dijkstra E. W. O notă despre două probleme în legătură cu graficele // Numer . Math / F. Brezzi - Springer Science + Business Media , 1959. - Vol. 1, Iss. 1. - P. 269-271. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF01386390
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmi: constructie si analiza = Introduction to Algorithms. - Ed. a II-a. - M .: „Williams” , 2006. - S. 1296. - ISBN 0-07-013151-1 .
Levitin A. V. Capitolul 9. Metode lacome: Algoritmul lui Dijkstra // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 189-195. — 576 p. — ISBN 978-5-8459-0987-9

Note

↑ Cazurile speciale ale unui grafic direcționat sunt grafice nedirecționate și mixte („parțial direcționate”).
↑ Pentru un grafic cu ponderi negative, se folosește un algoritm mai general - Algoritmul lui Dijkstra cu potențiale
↑ Vladimir Alekseev, Vladimir Talanov, Curs „Data Structures and Computation Models”, Lectura nr. 7: Binomial and Fibonacci Heaps // 26.09.2006, Intuit.ru
↑ Vladimir Alekseev, Vladimir Talanov, Curs „Structuri de date și modele de calcul”, Cursul nr. 8: grămezi subțiri // 26.09.2006, Intuit.ru

Algoritmi de căutare grafică
Metode neinformate	Căutare bidirecțională Căutare fascicul Prima căutare a lățimii lexicografice Lățimea prima căutare Căutare după criteriul de cost Profunzime prima căutare Căutare înapoi Caută prin urcare în vârf Căutare limitată la profunzime Căutare în profunzime cu aprofundare iterativă
Metode informate	Decuparea alfa beta Ramura și metoda legată Căutați după prima potrivire A* B* D* Găsirea unui punct de tranziție IDA* Căutare recurstivă pe primul cel mai bun meci SMA*
Comenzi rapide	Algoritmul undelor Algoritmul Bellman-Ford algoritmul lui Dijkstra Algoritmul Johnson algoritmul lui Levit Algoritmul Floyd-Warshall Căutare margine
Arborele de întindere minim	algoritmul lui Boruvka algoritmul lui Prim algoritmul lui Kruskal
Alte	Algoritmul British Museum Algoritmul Edmonds Traversarea copacilor Algoritmul celui mai apropiat vecin în problema vânzătorului ambulant