Dijkstra's Algorithm vs A* Search, Explained

Dijkstra’s algorithm finds the shortest path from a starting node to every other node in a weighted graph by expanding outward in all directions at once. A* search solves a narrower problem — the shortest path to one specific goal — by using a heuristic to bias that expansion toward the destination instead of exploring blindly. Both are guaranteed to find the optimal path under the right conditions; A* usually just gets there after visiting far fewer nodes.

How Dijkstra’s algorithm works

Dijkstra’s algorithm keeps a running table of the shortest known distance from the source to every node it has seen, plus a priority queue (see what a heap is for the structure that usually backs it) ordered by that distance. On each step it pulls the closest unvisited node, “relaxes” its neighbors — updating their distance if this path is shorter than what was previously known — and marks the node visited. It repeats until every reachable node has been finalized, or until the target is popped off the queue if you only care about one destination.

The key property is that it explores nodes in strict order of distance from the source. It never looks at a node before it has found the shortest way to reach it, which is exactly why it’s correct: once a node is popped, no shorter path to it can exist. This is a classic greedy algorithm — it commits to the locally best choice (the closest unvisited node) at every step, and that greedy choice happens to be globally optimal here because edge weights are non-negative.

The tradeoff is that Dijkstra doesn’t know where the goal is relative to the nodes it’s exploring. If you’re searching a road network for a route from Boston to Miami, Dijkstra will happily expand outward toward Seattle and Toronto before it ever turns south, because those nodes might be “closer” in accumulated edge weight even though they’re geographically irrelevant. It’s thorough, not directed.

How A* adds a heuristic

A* is Dijkstra’s algorithm plus one addition: a heuristic function h(n) that estimates the remaining distance from any node n to the goal. Instead of ordering the priority queue purely by the distance traveled so far (call it g(n)), A* orders it by f(n) = g(n) + h(n) — the cost so far plus the estimated cost still to come.

That estimate is what steers the search. If the heuristic is a straight-line distance on a map, nodes that point toward the destination get explored first, and nodes heading the wrong way get deprioritized even if they’re technically “cheap” by g(n) alone. The algorithm still maintains and updates a distance table exactly like Dijkstra’s; it’s the ordering of exploration that changes.

Why A* is usually faster

Dijkstra’s algorithm explores in expanding rings around the source, touching every node whose distance is less than or equal to the destination’s, regardless of direction. A* with a good heuristic collapses that ring into something closer to an elongated cone pointed at the goal, because nodes that clearly move away from the destination get pushed to the back of the queue. On a large graph — a road network, a game map, a pathfinding grid — that difference can mean visiting a small fraction of the nodes Dijkstra would touch to answer the same query.

The catch is that A*‘s advantage depends entirely on having a goal to aim at and a decent heuristic to estimate distance to it. If you need shortest paths from one source to every other node — the kind of all-pairs result a routing table or a graph database query might need — there’s no single destination to steer toward, and Dijkstra’s algorithm (or an all-pairs variant) is the right tool.

Admissible and consistent heuristics

A* only guarantees the optimal path if the heuristic is admissible: it never overestimates the true remaining cost. A straight-line distance is admissible for road travel because you can never get somewhere faster than a straight line, even though roads curve and detour. If a heuristic overestimates, A* can commit to a path that looks cheap early on but turns out worse, and it may return a suboptimal answer.

A stronger property, consistency (also called the triangle inequality), requires that for every edge, the heuristic’s estimate doesn’t drop by more than the edge’s actual cost. Consistent heuristics guarantee that once a node is popped from the queue, its shortest distance is final — the same property Dijkstra’s algorithm relies on — which avoids having to re-open and re-relax already-visited nodes. Most practical heuristics, like straight-line or Manhattan distance on a grid, are both admissible and consistent.

An admissible-but-inconsistent heuristic still finds the optimal path; it’s just less efficient, because nodes may need to be revisited when a cheaper path to them is discovered later.

Dijkstra vs A*: comparison table

	Dijkstra’s algorithm	A* search
Goal	Shortest path to all nodes (or one)	Shortest path to one specific goal
Ordering	By distance from source, g(n)	By g(n) + h(n), cost plus heuristic estimate
Needs a heuristic	No	Yes — quality determines efficiency
Nodes explored	Expands uniformly outward	Biased toward the goal
Optimality	Always optimal (non-negative weights)	Optimal if the heuristic is admissible
Best for	All-pairs or unknown-destination queries	Single-source, single-destination search

When to reach for each

Use Dijkstra’s algorithm when you need distances to many or all destinations from one source, when no domain-specific heuristic exists, or when correctness with the simplest possible mental model matters more than raw speed. Routing tables, network cost analysis, and anything resembling a general breadth-first or depth-first traversal problem with weighted edges tend to fall here.

Use A* when there’s a single well-defined goal and a heuristic you can trust to be admissible — pathfinding on a map, a game AI navigating a level, puzzle solvers like the sliding-tile problem where “tiles out of place” or “Manhattan distance to solved” work as heuristics. The better the heuristic approximates the true remaining cost, the closer A*‘s exploration gets to a straight line toward the answer; a heuristic of zero everywhere degrades A* back into plain Dijkstra’s algorithm, which is a useful way to remember that Dijkstra is really just a special case of A*.

Both run in roughly the same Big O time in the worst case — O((V + E) log V) with a binary heap — so the practical difference isn’t complexity class, it’s how much of the graph you actually have to touch before finding the answer.

The takeaway

Dijkstra’s algorithm and A* search solve the same underlying shortest-path problem, and A* is Dijkstra’s algorithm with a heuristic bolted on to aim the search at a known goal. Pick Dijkstra when you need distances to everywhere or don’t have a reliable heuristic; pick A* when there’s one destination and a heuristic — like straight-line distance — that never overestimates the remaining cost. Get the heuristic wrong and A* can return a wrong answer fast; get it right and it returns the right answer while touching a fraction of the nodes Dijkstra would.