Why Dijkstra Beat A* in My Tiny Maze

A* explored fewer nodes. Dijkstra still finished faster. That result looked wrong—until I stopped thinking only about Big-O notation and started thinking about the actual work done by the CPU.

The result that surprised me

I built a C++ maze visualizer to compare Dijkstra’s algorithm with A*. Both algorithms found the same shortest path, exactly as expected. A* also explored fewer cells because its heuristic guided it toward the destination.

But when I measured execution time, Dijkstra sometimes won by a few microseconds. The algorithm doing more searching was finishing first.

Why this happens

My maze is small enough that both algorithms finish almost immediately. At that scale, A*’s extra bookkeeping matters. For every candidate cell, it calculates a heuristic, combines it with the known path cost, and compares a more complex priority value.

Dijkstra has no heuristic. It expands nodes using only the distance already travelled. It may visit more of them, but each visit is slightly simpler.

The hardware does not read the textbook

Algorithm analysis tells us how performance grows as the input becomes large. It does not promise that the algorithm with the better growth pattern wins every tiny benchmark. Cache behaviour, branch prediction, priority-queue operations, compiler optimizations, clock precision, and normal system noise can dominate a measurement this small.

On larger mazes, or maps with expensive exploration, A*’s ability to avoid irrelevant regions becomes much more valuable. The saved search work eventually outweighs the heuristic overhead.

What I learned

The useful lesson was not that Dijkstra is better than A*. It was that theory and measurement answer different questions. Theory helps predict how a system scales. Profiling shows what this implementation is doing on this machine, with this input, right now.

Good engineering needs both.