When should I use A* instead of Dijkstra?

Use A* when you have a goal vertex and a useful heuristic (estimated remaining distance). A* expands far fewer nodes than Dijkstra by guiding the search toward the goal. Use Dijkstra when you need shortest paths from one source to all targets (no goal), or when no useful heuristic exists. The two have identical correctness guarantees with an admissible heuristic.

9 min read · Guide · Algorithms

How it works · Algorithms

How graph routing finds the shortest path.

Given a start vertex, a goal vertex and a weighted graph between them, three algorithms (Dijkstra, A* and Bellman–Ford) find the cheapest path, each with different trade-offs. The grid below runs Dijkstra and A* so you can compare how they search.

Parts01–08 InteractiveLive grid PrereqGraphs / queues

What is graph routing?

Finding the cheapest path between two points in a weighted graph.

Graph routing finds the shortest (or cheapest) path between two vertices in a weighted graph. The four classical algorithms (Dijkstra (1959), A* (Hart, Nilsson & Raphael, 1968), Bellman-Ford (1956-58), Floyd-Warshall (1962)) solve the same problem with different trade-offs around negative edges, heuristics, and all-pairs vs single-source.

The input is a graph of vertices and edges, where each edge has a non-negative cost, plus a start vertex and a goal vertex. The task is to find the path between them with minimum total cost. This is the shortest-path problem, and it appears in routing protocols, navigation apps, network flow, and dependency resolution.

Three classical algorithms cover the single-source case. Each handles a slightly different version of the problem and pays for its generality with extra work.

Dijkstra

Non-negative weights

The simplest and most common. It greedily expands the closest unvisited vertex. Optimal when all edge weights are ≥ 0. O((V+E) log V) with a binary heap.

With a heuristic

Dijkstra plus a heuristic that estimates remaining distance. Searches far less of the graph when the heuristic is admissible (never overestimates). Widely used in map and game pathfinding.

Bellman–Ford

Negative weights

Slower (O(V·E)) but tolerates negative edges and can detect negative cycles. Used in distance-vector routing protocols and currency-arbitrage detection.

Dijkstra and A* on a grid

Dijkstra fans out evenly; A* leans toward the goal.

The grid below is a graph: each cell is a vertex, every cell is connected to its four neighbours with weight 1, walls are missing edges. Pick start and goal, draw walls, then run. Compare Dijkstra (expands radially) and A* (biases toward the goal).

0 cells visited Dijkstra: radial

start goal wall frontier visited path

How Dijkstra's algorithm works

A priority queue and a relax step, repeated until the goal pops.

Dijkstra maintains a priority queue (a min-heap) of vertices keyed by tentative distance from the start. The loop pops the cheapest unvisited vertex; for each neighbour, if the path through this vertex is cheaper than the neighbour's current best, update it. Repeat until the goal is popped. The algorithm was devised in 1956 and has changed little since.

The greedy choice is safe because a vertex's distance is final once it is popped. No later relaxation can shorten it, since every unvisited vertex is at least as far away and all edges are non-negative, so adding an edge can never decrease the total. This is why negative edges break Dijkstra.

A* is Dijkstra plus a heuristic that never overestimates

Adding an estimate of the remaining distance steers the search.

A* is Dijkstra with a different priority: g(n) + h(n), where g is the actual cost from start and h is a heuristic estimate of cost from n to goal. The heuristic biases the search toward the goal, expanding far fewer vertices.

For A* to find the optimal path, the heuristic must be admissible, meaning it never overestimates the actual remaining cost. On a grid with four-way unit-cost moves, Manhattan distance is admissible because it is a lower bound. A stronger property, being consistent (monotonic), guarantees no vertex needs reopening. Most reasonable distance estimates satisfy both.

Bellman–Ford handles negative edges, at a cost

Slower than Dijkstra, but it copes with negative weights and detects negative cycles.

If even one edge can be negative, Dijkstra fails: its greedy guarantee breaks. Bellman–Ford relaxes every edge V−1 times, after which every shortest path is settled. If a further pass still relaxes anything, there is a negative cycle.

The cost is O(V·E), much slower than Dijkstra's O((V+E) log V) on typical graphs. Use Bellman–Ford when (a) the graph has negative weights, or (b) you need negative-cycle detection (financial arbitrage, currency conversion, distance-vector routing protocols like the kind BGP grew out of).

Floyd–Warshall: shortest paths between every pair

Three nested loops solve all-pairs shortest paths in O(V³).

Sometimes you need shortest paths between every pair of vertices, not just one source. Running Dijkstra from every vertex is one approach (V × O(E log V)). The alternative, Floyd–Warshall, uses dynamic programming to do all pairs in O(V³).

For dense graphs (E close to V²), Floyd–Warshall wins. For sparse graphs (E close to V), repeated Dijkstra wins. Floyd–Warshall also handles negative edges and detects negative cycles, and it is only three nested loops.

Where these algorithms run: maps, routers, builds

The same primitives appear in navigation, networking and build tools.

Maps

Contraction hierarchies

Plain A* or Dijkstra on a continent-scale road network is too slow. Modern map apps preprocess the graph into a contraction hierarchy, so long stretches of road become single shortcut edges. Routing across Europe takes well under a second.

Routers

Bellman–Ford in distributed form

RIP, EIGRP, and BGP's path-vector cousins are distance-vector protocols, which run Bellman–Ford in a distributed way. Each router relaxes its neighbours' tables until the network converges. See the BGP guide.

Builds

Topological order and critical path

Build systems such as Bazel and Buck walk the dependency DAG in topological order, and critical-path analysis (a longest-path variant) shows which targets limit build time. The graph is your codebase's dependency tree.

How to choose a shortest-path algorithm

Four questions about your graph decide it.

Negative weights? Bellman–Ford. Need a goal-biased search and a usable heuristic? A*. Otherwise, single-source non-negative? Dijkstra. All-pairs on a small dense graph? Floyd–Warshall.

Most other shortest-path algorithms (Yen's, contraction hierarchies, ALT, transit-node routing) build on one of these four. Knowing them is enough to read most production routing code.

Graph routing in production: Maps, OSPF, Uber, parcels

How real systems scale shortest-path to very large graphs.

Google Maps / Apple Maps / OSRM: Real road graphs have hundreds of millions of nodes or more; plain Dijkstra is too slow. Production uses contraction hierarchies (Geisberger et al., 2008): a precomputed shortcut graph that answers point-to-point queries in milliseconds. OSRM ships an open implementation; Google's internal version is custom.
OSPF / IS-IS · interior routing: Inside an autonomous system, every router runs Dijkstra over the link-state database every few seconds. Convergence times: ~1-3 seconds for OSPF in a typical enterprise; sub-second with BFD-driven failure detection.
Uber dispatch: Match riders to drivers via shortest-path on a road graph + time-of-day traffic estimates. Uber's H3 hexagonal grid system reduces graph size for citywide computations. Described on Uber's engineering blog (2018).
UPS / FedEx / DHL package routing: Vehicle Routing Problem (VRP): generalises shortest path to multi-stop tours with capacity constraints. Solved via specialised heuristics (Clarke-Wright savings) plus shortest-path subroutines. UPS ORION saved ~$300M/year by reducing routes ~10%.
Network packet forwarding: Internet routers store FIBs (Forwarding Information Bases) computed from routing-table shortest paths; lookup uses tries (longest-prefix match) at line rate. The path computation runs on the route processor; the data plane just looks up.

A closing note

Shortest-path is a small problem with a lot of practical uses. Most routing systems are one of the four classical algorithms with added caching, parallelism, a better queue or a better heuristic. The grid above uses the same algorithms that pick your bike route.