Dijkstra (vážená mřížka)

O(E log V)

Tohle je Dijkstrův algoritmus nejkratší cesty na mřížce, kde má každá buňka vstupní cenu — běžné buňky stojí 1, hnědé "těžké" buňky stojí 5. Vždy rozvine dosud nejlevněji dosažitelnou nenavštívenou buňku a usazuje buňky v pořadí rostoucí celkové ceny. Protože volbu řídí cena, ne počet kroků, nejlevnější cesta se často ohne kolem oblasti těžkého terénu místo aby jí prošla rovnou — přesně tam se liší od BFS, které počítá jen kroky. S min-prioritní frontou běží v O(E log V). Klikni pro přidání zdí; těžký pás je pevný, ať vidíš, jak trasa preferuje levnější obchvat.

Klikni na buňku pro přepnutí zdi
Mřížka
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Dej startu cenu 0 a každé jiné buňce nekonečno.
  2. Rozviň nenavštívenou buňku s dosud nejmenší cenou.
  3. Pro každého souseda je nová cena tahle cena plus vstupní cena souseda.
  4. Je-li levnější, zaznamenej ji. Konečná cena cíle je nejlevnější trasa — vystopuj ji zpět.

Pseudokód

1dijkstraGrid(grid, start, goal):     # O(E log V)2  dist[start] ← 0; rest ← ∞3  while cells remain:4    cell ← unvisited cell with least dist5    if cell = goal: stop6    for nbr in open neighbours(cell):7      nd ← dist[cell] + cost(nbr)      # cost = terrain weight8      if nd < dist[nbr]: dist[nbr] ← nd; prev[nbr] ← cell9  walk prev back — cheapest, not fewest steps