Dijkstra and A*: Shortest Path Algorithms Explained

Graphs, weights, and relaxation

A graph G = (V, E) consists of vertices and edges; in a weighted graph, each edge (u, v) carries a non-negative cost w(u,v) representing distance, time, or some other penalty. Shortest-path algorithms find the minimum-cost path from a source to one or all other vertices, and nearly all of them share the same core operation, relaxation: if a newly discovered route to v is cheaper than the best one known so far, update it.

Relaxation:
  if d[v] > d[u] + w(u,v):
      d[v] = d[u] + w(u,v)
      parent[v] = u

d[v] = current best known distance from source to v
Initially: d[s] = 0, d[v] = ∞ for all other v

Dijkstra's algorithm

Dijkstra (1959) processes vertices in order of their tentative shortest distance using a priority queue: repeatedly extract the vertex with the smallest known distance, and relax every edge leading out of it. Because edge weights are non-negative, once a vertex is extracted its distance is provably final — no unprocessed vertex could ever offer a cheaper route to it. That guarantee breaks the moment a negative edge weight is allowed, which is why Dijkstra needs Bellman-Ford (O(VE), handles negative weights, detects negative cycles) as a fallback. Performance depends heavily on the priority queue: an unsorted array gives O(V²), suitable for dense graphs; a binary heap gives O((V+E) log V), the practical choice for the sparse graphs typical of road networks, where a binary-heap Dijkstra over a million-node city map runs in roughly 50-100ms.

A* search and heuristics

A* (Hart, Nilsson, Raphael, 1968) improves Dijkstra for single-target searches by adding a heuristic h(v), an estimate of the remaining cost from v to the goal:

f(v) = g(v) + h(v)
  g(v) = exact cost from source to v   (same as Dijkstra's d[v])
  h(v) = heuristic estimate of cost from v to the goal

Common heuristics:
  Euclidean distance:  h(v) = √((x_v−x_t)² + (y_v−y_t)²)
  Manhattan distance:  h(v) = |x_v−x_t| + |y_v−y_t|   (grid graphs)

Dijkstra explores in concentric circles around the source; A*, sorting its priority queue by f instead of g, explores an ellipse stretched toward the goal — typically 5 to 100 times fewer nodes expanded on road-network-style graphs. The guarantee that A* still finds the truly optimal path depends on admissibility: h(v) must never overestimate the real remaining cost. Euclidean and Manhattan distance are both admissible (and consistent, satisfying a triangle inequality that avoids re-opening nodes); a heuristic that always returns zero is trivially admissible and reduces A* to plain Dijkstra. Weighted variants like f = g + w·h with w > 1 are inadmissible but faster, guaranteeing only a path within (1+ε) of optimal — a common trade-off in real-time game AI.

Variants and real-world use

Production systems layer further tricks on top: bidirectional search runs from both source and target and meets in the middle; Jump Point Search prunes huge numbers of intermediate nodes on uniform-cost grids for a 10-100× speedup; Contraction Hierarchies precompute shortcut edges offline so a 1,000km route query on a continental road network takes under a millisecond. Google Maps, Apple Maps and Waze combine variants of these with live traffic data. Game engines run thousands of A* queries per second over navigation meshes for NPC pathfinding, internet routers run Dijkstra directly on link-state databases for OSPF routing, and robots use D* Lite to replan efficiently as their map of the world changes — the same core idea, discovered in 1956, still routing planes, packets and pixels today.

Frequently asked questions

Try it live

Everything above runs in your browser — open Pathfinding — A*, Dijkstra, BFS, draw walls or generate a maze, and watch A*, Dijkstra, Greedy Best-First and BFS explore the grid step by step. Nothing is installed, nothing is uploaded.