Dijkstras algoritm
Hittar den billigaste vägen från en start till ett mål. Den tar alltid den billigaste platsen som väntar i en prioritetskö, så kostnaderna sprider sig från starten som en flod.
- tid O((V + E) log V)
- minne O(V)
- använder en prioritetskö
Vad betyder det här?
- Kostnad: vad ett drag kostar. I labyrinten kostar mark 1, lera 3 och vatten 9; i grafen talet på kanten.
- Prioritetskö: en kö där den billigaste går först, inte den som kom först.
- Uppskattning (h): en gissning av kostnaden som återstår. A* förblir exakt bara om den aldrig är för hög.
- Att relaxera en kant: kontrollera om vägen via den aktuella platsen ger en granne lägre kostnad, och i så fall ta den.
- i kön
- aktuell
- klar
- billigaste väg
- mark · 1
- lera · 3
- vatten · 9
- vägg
Ny: Start i A1 med kostnad 0. Den är det enda i kön.
Blanksteg: spela upp eller pausa. Vänster och höger pil: steg. Home och End: hoppa.
Prova det här: Välj kärret. Den billigaste vägen går runt hela leran: dubbelt så många drag som den raka linjen, och ändå billigare (34 mot 36).
Så fungerar det
Varje plats får en kostnad: 0 för starten, oändligt för resten. Dijkstra håller de nådda platserna i en prioritetskö och tar alltid den billigaste. Den kostnaden är då slutgiltig, eftersom varje annan väg dit skulle behöva gå via något minst lika dyrt. Sedan tittar den på varje granne: om vägen via platsen den nyss tog är billigare än grannens hittillsvarande kostnad, får grannen den nya kostnaden och minns varifrån den kom. När målet är taget leder de länkarna tillbaka längs den billigaste vägen.
När det är ett bra val
Använd Dijkstra när drag kostar olika mycket och inget kostar mindre än noll: vägkartor och navigatorer, routning i nätverk, den billigaste flygkombinationen. Kostar alla drag lika mycket ger BFS samma svar enklare. Med negativa kostnader kan Dijkstra ha fel; för dem finns Bellman-Ford.