Dijkstrův algoritmus
Najde nejlevnější cestu ze startu do cíle. Vždy vezme nejlevnější místo čekající v prioritní frontě, takže se náklady šíří od startu jako povodeň.
- čas O((V + E) log V)
- paměť O(V)
- používá prioritní frontu
Co to znamená?
- Cena: kolik stojí tah. V bludišti stojí zem 1, bahno 3 a voda 9; v grafu číslo na hraně.
- Prioritní fronta: fronta, ve které jde první nejlevnější, ne ten, kdo přišel první.
- Odhad (h): předpověď zbývající ceny. A* zůstává přesný, jen když není nikdy moc vysoký.
- Relaxace hrany: ověření, zda cesta přes aktuální místo dá sousedovi nižší cenu, a pokud ano, její převzetí.
- ve frontě
- aktuální
- hotový
- nejlevnější cesta
- zem · 1
- bahno · 3
- voda · 9
- zeď
Nový: Start v A1 s cenou 0. Je jediný ve frontě.
Mezerník: přehrát nebo pozastavit. Šipky vlevo/vpravo: krok. Home a End: přeskočit.
Zkuste: Vyberte bažinu. Nejlevnější cesta obchází celé bahno: dvakrát víc tahů než přímka, a přesto levnější (34 proti 36).
Jak to funguje
Každé místo dostane cenu: start 0, zbytek nekonečno. Dijkstra drží dosažená místa v prioritní frontě a vždy vezme nejlevnější. Jeho cena je pak konečná, protože každá jiná cesta by musela vést přes něco aspoň stejně drahého. Potom projde sousedy: když je cesta přes právě vzaté místo levnější než dosavadní cena souseda, soused dostane novou cenu a zapamatuje si, odkud přišel. Když algoritmus vezme cíl, tyto odkazy vedou zpět po nejlevnější cestě.
Kdy se hodí
Dijkstru použijte, když tahy stojí různě a žádný méně než nula: silniční mapy a navigace, směrování v sítích, nejlevnější kombinace letů. Když každý tah stojí stejně, BFS dá stejnou odpověď jednodušeji. Se zápornými cenami se Dijkstra může splést; na ty je Bellman–Ford.