Dijkstrov algoritmus
Nájde najlacnejšiu cestu zo štartu do cieľa. Vždy vezme najlacnejšie miesto čakajúce v prioritnom rade, takže sa náklady šíria od štartu ako povodeň.
- čas O((V + E) log V)
- pamäť O(V)
- používa prioritný rad
Čo to znamená?
- Cena: koľko stojí ťah. V bludisku stojí zem 1, blato 3 a voda 9; v grafe číslo na hrane.
- Prioritný rad: rad, v ktorom ide prvý najlacnejší, nie ten, kto prišiel prvý.
- Odhad (h): predpoveď zostávajúcej ceny. A* zostáva presný, len keď nie je nikdy priveľký.
- Relaxácia hrany: overenie, či cesta cez aktuálne miesto dá susedovi nižšiu cenu, a ak áno, jej prevzatie.
- v rade
- aktuálny
- hotový
- najlacnejšia cesta
- zem · 1
- blato · 3
- voda · 9
- stena
Nový: Štart v A1 s cenou 0. Je jediný v rade.
Medzerník: prehrať alebo pozastaviť. Šípky vľavo/vpravo: krok. Home a End: preskočiť.
Skúste: Vyberte močiar. Najlacnejšia cesta obchádza celé blato: dvakrát viac ťahov ako priamka, a predsa lacnejšia (34 oproti 36).
Ako to funguje
Každé miesto dostane cenu: štart 0, zvyšok nekonečno. Dijkstra drží dosiahnuté miesta v prioritnom rade a vždy vezme najlacnejšie. Jeho cena je potom konečná, pretože každá iná cesta by musela viesť cez niečo aspoň rovnako drahé. Potom prejde susedov: ak je cesta cez práve vzaté miesto lacnejšia ako doterajšia cena suseda, sused dostane novú cenu a zapamätá si, odkiaľ prišiel. Keď algoritmus vezme cieľ, tieto odkazy vedú späť po najlacnejšej ceste.
Kedy sa hodí
Dijkstru použite, keď ťahy stoja rôzne a žiadny menej ako nula: cestné mapy a navigácie, smerovanie v sieťach, najlacnejšia kombinácia letov. Keď každý ťah stojí rovnako, BFS dá rovnakú odpoveď jednoduchšie. So zápornými cenami sa Dijkstra môže pomýliť; na tie je Bellman–Ford.