Algoritmul lui Dijkstra

Planificatorul de rute știe cel mai rapid drum de la ușa dumneavoastră până aproape oriunde. În centrul acestei idei se află un algoritm pe care Edsger Dijkstra l-a conceput în vreo douăzeci de minute în 1956: porniți de la start spre exterior și terminați mereu întâi locul cel mai apropiat.

Un graf ale cărui muchii au lungimi, cu nodurile apropiate de start terminate în verde, un arbore al celor mai scurte drumuri și o coadă de priorități desenată dedesubt
Un graf ale cărui muchii au lungimi, cu nodurile apropiate de start terminate în verde, un arbore al celor mai scurte drumuri și o coadă de priorități desenată dedesubt

Ideea

Imaginați-vă orașe legate prin drumuri de lungimi diferite. Întrebarea este: care este cel mai scurt drum de la orașul meu la fiecare dintre celelalte? Căutarea în lățime răspunde atunci când fiecare drum contează la fel, dar aici o rută cu mai multe drumuri poate fi mai scurtă. Algoritmul lui Dijkstra păstrează pentru fiecare oraș cea mai mică distanță găsită până acum și extinde o regiune de orașe a căror distanță este sigură, adăugând mereu cel mai apropiat oraș care nu este încă sigur.

Pas cu pas

Dați startului distanța 0 și fiecărui alt nod infinit. Puneți startul într-o coadă de priorități, o coadă care dă mereu nodul cu cea mai mică distanță. Luați acel nod; distanța lui este acum definitivă. Pentru fiecare vecin care nu este definitiv, calculați distanța prin acest nod: distanța nodului plus lungimea muchiei. Dacă este mai mică decât distanța de până acum a vecinului, micșorați-o, rețineți acest nod ca drum până acolo și puneți vecinul în coadă. Aceasta se numește relaxarea unei muchii. Repetați până când coada este goală sau până când ținta este luată din ea.

Un exemplu

Luați muchiile A–B de lungime 4, A–C 1, B–C 2, B–D 1, C–D 5 și D–E 3 și porniți din A. Luarea lui A îi dă lui B distanța 4 și lui C distanța 1. C este cel mai apropiat, deci este definitiv la 1; prin C, B scade la 1 + 2 = 3, iar D primește 1 + 5 = 6. Acum B este cel mai apropiat, definitiv la 3, iar prin B, D scade la 3 + 1 = 4. D este definitiv la 4 și îi dă lui E 4 + 3 = 7. Deci cel mai scurt drum de la A la E este A → C → B → D → E, de lungime 7, deși A → B → D → E folosește mai puține muchii și are lungimea 8.

De ce este corect

Să presupunem că nodul X este cel mai apropiat din coadă, la distanța d. Orice alt drum de la start la X trebuie să părăsească la un moment dat regiunea nodurilor definitive, iar primul nod pe care îl atinge în afara acelei regiuni este în coadă, deci este deja la cel puțin d. Restul drumului nu îl poate scurta, pentru că nicio muchie nu este negativă. Deci d este cea mai mică distanță până la X. Cu o muchie negativă argumentul nu mai funcționează; atunci se folosește algoritmul Bellman–Ford, care relaxează fiecare muchie din nou și din nou.

Istorie și utilizări

Edsger W. Dijkstra a conceput algoritmul în 1956 pentru a prezenta un calculator nou, ARMAC din Amsterdam, găsind rute între orașe olandeze, și l-a publicat în 1959. Aceeași idee, cu o coadă mai inteligentă, rulează în planificatoarele de rute și în protocoalele de rutare de pe internet, precum OSPF și IS-IS, care calculează cel mai scurt drum pentru date între routere. Căutarea A* adaugă o estimare a distanței rămase, astfel încât se poate îndrepta spre țintă și poate examina mai puține noduri.

Edsger W. Dijkstra la tablă
Edsger W. Dijkstra la tablă

Explorați

Deschideți aplicația și apăsați Pas. Numerele de pe muchii sunt lungimile lor, iar numărul de pe fiecare nod este distanța lui de până acum. Nodurile din coadă sunt albastre, cele definitive verzi, iar coada de sub graf le enumeră cu distanțele lor, cel mai apropiat primul. Urmăriți momentele în care o distanță scade pentru că o rută care pare mai lungă se dovedește mai scurtă și alegeți o țintă pentru a vedea căutarea oprindu-se imediat ce ținta este definitivă.

Întrebări frecvente

Care este complexitatea în timp a algoritmului lui Dijkstra?

Depinde de coada de priorități. Cu o listă simplă este O(V²) pentru V noduri; cu un heap binar O((V + E) log V) pentru E muchii; cu un heap Fibonacci O(E + V log V), după cum au arătat Michael Fredman și Robert Tarjan în 1984.

Poate algoritmul lui Dijkstra să lucreze cu ponderi negative ale muchiilor?

Nu. Presupune că distanța unui nod nu se mai poate îmbunătăți odată ce nodul este cel mai apropiat din coadă, iar o muchie negativă poate încălca asta. Folosiți algoritmul Bellman–Ford pentru grafuri cu muchii negative.

Găsește algoritmul lui Dijkstra drumul către fiecare nod?

Da. Rulat până la capăt, dă cea mai mică distanță de la start la fiecare nod care poate fi atins, iar nodurile reținute formează un arbore al celor mai scurte drumuri. Oprirea mai devreme, când ținta este definitivă, economisește muncă atunci când e nevoie de un singur drum.

Ce legătură are algoritmul lui Dijkstra cu A*?

Căutarea A* este algoritmul lui Dijkstra cu un indiciu: ordonează coada după distanța de până acum plus o estimare a distanței rămase, de exemplu distanța în linie dreaptă pe o hartă. Cu o estimare bună găsește același cel mai scurt drum, examinând mult mai puține noduri.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Încercați algoritmul lui Dijkstra