Dijkstran algoritmi
Löytää halvimman reitin lähdöstä maaliin. Se ottaa aina halvimman prioriteettijonossa odottavan paikan, joten kustannukset leviävät lähdöstä kuin tulva.
- aika O((V + E) log V)
- tila O(V)
- käyttää prioriteettijonoa
Mitä nämä tarkoittavat?
- Kustannus: mitä siirto maksaa. Sokkelossa maa maksaa 1, muta 3 ja vesi 9; graafissa kaaren luku.
- Prioriteettijono: jono, jossa halvin menee ensin, ei ensimmäisenä tullut.
- Arvio (h): arvaus jäljellä olevasta kustannuksesta. A* pysyy tarkkana vain, jos se ei ole koskaan liian suuri.
- Kaaren relaksointi: tarkistetaan, antaako kulku nykyisen paikan kautta naapurille pienemmän kustannuksen, ja otetaan se, jos antaa.
- jonossa
- nykyinen
- valmis
- halvin reitti
- maa · 1
- muta · 3
- vesi · 9
- seinä
Uusi: Lähtö ruudusta A1, kustannus 0. Se on ainoa jonossa.
Välilyönti: toisto tai tauko. Nuolinäppäimet: askel. Home ja End: alkuun tai loppuun.
Kokeile tätä: Valitse suo. Halvin reitti kiertää koko mudan: kaksi kertaa niin monta siirtoa kuin suora viiva, ja silti halvempi (34 vastaan 36).
Miten se toimii
Jokainen paikka saa kustannuksen: lähtö 0, muut ääretön. Dijkstra pitää saavutetut paikat prioriteettijonossa ja ottaa aina halvimman. Sen kustannus on silloin lopullinen, koska mikä tahansa muu reitti sinne kulkisi jonkin vähintään yhtä kalliin kautta. Sitten se katsoo jokaisen naapurin: jos kulku juuri otetun paikan kautta on halvempi kuin naapurin tähänastinen kustannus, naapuri saa uuden kustannuksen ja muistaa, mistä tuli. Kun maali on otettu, nämä merkinnät johtavat halvinta reittiä takaisin.
Milloin se on hyvä valinta
Käytä Dijkstraa, kun siirrot maksavat eri verran eikä mikään alle nollan: tiekartat ja navigaattorit, verkkojen reititys, halvin lentoyhdistelmä. Jos jokainen siirto maksaa saman verran, BFS antaa saman vastauksen yksinkertaisemmin. Negatiivisilla kustannuksilla Dijkstra voi erehtyä; niille on Bellman–Ford.