Shortest Path Algorithms: Dijkstra, A* and Pathfinding in Games
Originally published in April 2022. Updated October 2026. Finding the best route between two points sounds simple until the map contains hundreds of intersections, roads with different travel costs, and areas that should be avoided altogether. This is the shortest-path problem: given a graph and a cost for traversing each edge, find a path whose total cost is minimal. In this article, we’ll use a small graph to explore two classic shortest-path algorithms: Dijkstra’s algorithm and A search*. We’ll start with the fundamentals of graph theory and briefly explore breadth-first search (BFS), depth-first search (DFS), and Bellman–Ford before examining Dijkstra and A* step by step. ...