Dijkstra and A* shortest path

The articles written on this blog were created with the goal of teaching. Also, the information in the article may be incorrect, so please be careful.

If the movement cost is different for each tile, simple BFS alone cannot guarantee the cheapest route. At this time, shortest path algorithms such as Dijkstra and A* are used.

Dijkstra

The vertex with the lowest cumulative cost from the starting point to the present is expanded first.

New Cost = Current Cost + Next Trunk Cost

If the new cost is less than the old record
Update distance and previous vertices.

When using Priority Queue, generallyO((V + E) log V)It can be implemented to that extent. The default Dijkstra should not be used because the presence of negative edges may reduce the already established shortest distance.

A*

A* is the actual cost from the starting pointgand the estimated cost to reach the goal.hAdd to determine priorities.

f(n) = g(n) + h(n)

In grids, Manhattan Distance or Euclidean Distance can be used as a heuristic. For hexagonal grids, a distance function appropriate for hexagonal coordinates must be used.

The shortest path can be guaranteed if the estimated cost does not overestimate the actual lowest remaining cost. If Heuristic is 0, A* behaves like Dijkstra.

Which one to use?

Requires multiple destination costs from one starting point: Dijkstra
Quickly navigate to one destination: A*
All trunk costs are the same: BFS

Path search performance is not determined by the algorithm name alone. Neighbor generation cost, obstacle representation, priority queue, and heuristic quality must also be checked.