Dijkstra vs A*: shortest paths, useful heuristics and the cost of searching

Dijkstra settles the cheapest tentative distance

Dijkstra’s algorithm starts with distance zero at the source and unknown distances elsewhere. It repeatedly selects the unvisited node with the smallest tentative distance, marks that distance final and tries improving neighbouring distances through it. The key assumption is that edge weights are nonnegative: an unexplored continuation cannot later supply a cheaper route through a negative surprise.

Trace the Dijkstra graph one step at a time. Watch a direct tentative route improve through an intermediate node. Dijkstra’s original shortest-path note is the primary reference. The authored network is deliberately small so every update is inspectable. Its cheapest path has more edges than some alternatives, illustrating why fewest connections and lowest accumulated weight are not the same objective when edges have different costs.

A* adds an estimate of what remains

A* prioritises states by g + h: the cost already incurred plus a heuristic estimate of remaining cost. A useful estimate can focus exploration toward the goal. Conditions such as admissibility and consistency matter for shortest-path guarantees, along with details of how the search handles previously examined states.

In the A* maze, moves are orthogonal and each costs one. Manhattan distance counts the minimum horizontal and vertical moves in the absence of walls. It never overstates the remaining path cost here and is consistent. Hart, Nilsson and Raphael’s original paper provides the formal heuristic-search framework. The board exposes a weight on this estimate: zero removes its guidance, one uses the valid grid heuristic and three overweights it. The latter is a different tradeoff, not a stronger optimality guarantee.

Worked example: keep route quality and search work separate

Use the built-in maze first so the terrain remains constant across comparisons. The returned path length is counted in unit moves; expanded cells report the work visible in this implementation. These are algorithmic counts, not browser timing benchmarks.

1. Choose heuristic weight zero and find a route. Record its length and the number of expanded cells, retaining the original wall layout. This is uniform-cost search on the unit grid, without a directional estimate.
2. Choose weight one, which restarts the same map, and search again. Compare both outputs. The admissible consistent estimate preserves shortest-path correctness here, while its guidance can change how many cells are expanded.
3. Choose weight three and inspect the actual returned route. Then edit walls and repeat. It may match the shortest path on a particular map, but that observation does not restore a general shortest-path guarantee for an overweighted heuristic.

The modelled cost needs to match the real task

A grid’s one-unit step is a modelling choice. Actual routes can have different travel times, risks, tolls or accessibility constraints. If the cost function omits what the user values, solving it perfectly may still produce an unsuitable route. Similarly, a heuristic that was valid for one movement rule can become invalid when diagonal moves or cheaper long connections are added.

Before optimising the search implementation, define the state, available actions, edge costs and success condition. Decide what happens when no route exists. The Modic maze exhausts its frontier and reports no route rather than drawing a line through a wall. That failure case is part of correctness. Search quality is easier to assess when the algorithm’s objective and the application’s actual requirement have been written in the same terms.

A review checklist for heuristic search

A visually direct route can be expensive and a fast-looking animation can conceal extensive computation. Use observable counts and stated guarantees instead of impressions. When comparing implementations, keep the graph, start, goal and cost model fixed; when changing those inputs, describe the comparison as a new task rather than evidence that the previous result was wrong.

• Specify whether the objective is edge count, distance, time or another accumulated cost.
• Check that nonnegative weights support Dijkstra’s settling argument.
• Show why the heuristic is a lower bound under the actual movement and cost rules.
• Report returned path cost separately from expansions, memory use and measured runtime.
• Test unreachable goals and changed maps, and state when a weighted heuristic sacrifices optimality.

No universal winner without a task distribution

The no free lunch activity provides a useful companion question. Two search orders have equal average probe costs across a tiny uniform unrestricted family of binary objectives. Restrict the family to ordered objectives and one order becomes better. The advantage comes from structure in the task family, not from a universal claim that one direction is inherently smarter.

That finite illustration is not a theorem about every practical path planner. Its connection is methodological: identify what structure justifies your chosen method. A* uses a goal-distance estimate because spatial structure can be useful. Dijkstra remains a clean baseline when that guidance is unavailable or inappropriate. The most informative comparison explains why the assumptions fit the task, measures the outcomes the application needs and preserves the guarantee that the implementation actually supplies.