Algoritme van Dijkstra
Vindt de goedkoopste weg van een start naar een doel. Neemt altijd de goedkoopste plek die in een prioriteitswachtrij wacht, zodat de kosten zich als een vloedgolf vanaf de start verspreiden.
- tijd O((V + E) log V)
- geheugen O(V)
- gebruikt een prioriteitswachtrij
Wat betekent dit?
- Kosten: wat een zet kost. In het doolhof kost grond 1, modder 3 en water 9; in de graaf het getal op de kant.
- Prioriteitswachtrij: een wachtrij waarin de goedkoopste eerst gaat, niet wie het eerst kwam.
- Schatting (h): een gok van de resterende kosten. A* blijft alleen exact als die nooit te hoog is.
- Een kant relaxeren: nagaan of de weg via de huidige plek een buur lagere kosten geeft, en die dan overnemen.
- in de wachtrij
- huidige
- afgerond
- goedkoopste weg
- grond · 1
- modder · 3
- water · 9
- muur
Nieuw: Start bij A1 met kosten 0. Het is het enige in de wachtrij.
Spatie: afspelen of pauzeren. Pijltjes links/rechts: stap. Home en End: springen.
Probeer dit: Kies het moeras. De goedkoopste weg gaat helemaal om de modder heen: twee keer zoveel zetten als de rechte lijn en toch goedkoper (34 tegen 36).
Hoe het werkt
Elke plek krijgt kosten: 0 voor de start, oneindig voor de rest. Dijkstra houdt de bereikte plekken in een prioriteitswachtrij en neemt altijd de goedkoopste. Die kosten staan dan vast, want elke andere weg ernaartoe zou langs iets minstens zo duurs moeten gaan. Daarna bekijkt hij elke buur: is de weg via de net genomen plek goedkoper dan de huidige kosten van de buur, dan krijgt de buur de nieuwe kosten en onthoudt waar hij vandaan kwam. Is het doel genomen, dan leiden die verwijzingen langs de goedkoopste weg terug.
Wanneer het een goede keuze is
Gebruik Dijkstra als zetten verschillend kosten en geen enkele minder dan nul: wegenkaarten en navigatie, routering in netwerken, de goedkoopste vluchtcombinatie. Kost elke zet evenveel, dan geeft BFS hetzelfde antwoord eenvoudiger. Met negatieve kosten kan Dijkstra het mis hebben; daarvoor is er Bellman-Ford.