Algoritmul lui Dijkstra
Găsește cel mai ieftin drum de la start la țintă. Ia mereu locul cel mai ieftin care așteaptă într-o coadă de prioritate, așa că costurile se întind de la start ca o inundație.
- timp O((V + E) log V)
- memorie O(V)
- folosește o coadă de prioritate
Ce înseamnă acești termeni?
- Cost: cât costă o mutare. În labirint, pământul costă 1, noroiul 3 și apa 9; în graf, numărul de pe muchie.
- Coadă de prioritate: o coadă în care trece întâi cel mai ieftin, nu cel venit primul.
- Estimare (h): o presupunere a costului rămas. A* rămâne exact doar dacă nu e niciodată prea mare.
- Relaxarea unei muchii: verificarea dacă trecerea prin locul curent dă unui vecin un cost mai mic și, dacă da, preluarea lui.
- în coadă
- curent
- gata
- cel mai ieftin drum
- pământ · 1
- noroi · 3
- apă · 9
- zid
Nou: Start în A1 cu costul 0. E singurul din coadă.
Space: redă sau pauză. Săgețile stânga și dreapta: pas cu pas. Home și End: salt.
Încearcă: Alege mlaștina. Drumul cel mai ieftin ocolește tot noroiul: de două ori mai multe mutări decât linia dreaptă și totuși mai ieftin (34 față de 36).
Cum funcționează
Fiecare loc primește un cost: 0 pentru start, infinit pentru rest. Dijkstra ține locurile atinse într-o coadă de prioritate și îl ia mereu pe cel mai ieftin. Costul lui devine atunci definitiv, pentru că orice alt drum ar trebui să treacă prin ceva cel puțin la fel de scump. Apoi se uită la fiecare vecin: dacă trecerea prin locul abia luat e mai ieftină decât costul de până acum al vecinului, vecinul primește noul cost și ține minte de unde a venit. Când ținta e luată, aceste legături duc înapoi pe drumul cel mai ieftin.
Când este o alegere bună
Folosește Dijkstra când mutările costă diferit și niciuna mai puțin de zero: hărți rutiere și GPS, rutare în rețele, cea mai ieftină combinație de zboruri. Dacă toate mutările costă la fel, BFS dă același răspuns mai simplu. Cu costuri negative Dijkstra poate greși; pentru ele există Bellman-Ford.