Dijkstra and A*: Shortest Path Algorithms Explained

Finding the shortest path between two points is one of the most practically useful problems in computer science. Edsger Dijkstra solved it in 1956. A few decades later, A* made it faster using spatial intuition. Together they power GPS navigation, game AI, robot motion planning, and network routing.

1. Graphs: Vertices, Edges, and Weights

A graph G = (V, E) consists of vertices (nodes) V and edges E. In a weighted directed graph, each edge (u, v) has a non-negative cost w(u,v) ≥ 0 representing distance, time, or some penalty. The shortest-path problem: find the minimum-cost path from source s to any or all destinations.

Single-source shortest path (SSSP): Find shortest paths from one source to all other vertices. Solved by Dijkstra and Bellman-Ford.
Single-pair shortest path: From s to t. A* is optimised for this.
All-pairs shortest path (APSP): Between all vertex pairs. Floyd-Warshall: O(V³).

Relaxation (the key operation): 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] = \infty for all other v

2. Dijkstra's Algorithm

Dijkstra (1959) processes vertices in order of their tentative shortest distance, using a priority queue:

Dijkstra's Algorithm: DIJKSTRA(G, w, s): d[s] = 0; d[v] = \infty for v \neq s Q = min-priority queue containing all vertices keyed by d[v] while Q not empty: u = EXTRACT-MIN(Q) # vertex with smallest d[u] for each neighbour v of u: if d[u] + w(u,v) < d[v]: d[v] = d[u] + w(u,v) # relaxation parent[v] = u DECREASE-KEY(Q, v, d[v]) Correctness proof (informal): When u is extracted from Q, d[u] is FINAL (cannot be improved). Proof: if there were a shorter path, it would pass through some unprocessed vertex x with d[x] \geq d[u] \to total path \geq d[u]. Therefore d[u] is optimal at extraction time. QED. (Requires non-negative edge weights!)

Dijkstra on negative weights: Dijkstra fails with negative-weight edges because the greedy extraction assumption breaks. Use Bellman-Ford instead: O(VE) complexity, handles negative weights, and detects negative cycles. Practical in financial arbitrage detection and routing protocols like OSPF (which uses Dijkstra on positive-link-cost networks).

3. Complexity and Data Structures

Dijkstra complexity depends on priority queue implementation: ┌───────────────────────┬────────────┬────────────────────────────┐ │ Priority Queue │ Total Time │ Best for │ ├───────────────────────┼────────────┼────────────────────────────┤ │ Array (unsorted) │ O(V²) │ Dense graphs (E \approx V²) │ │ Binary heap │ O((V+E) log V) │ Sparse graphs │ │ Fibonacci heap │ O(E + V log V) │ Theoretical optimum │ └───────────────────────┴────────────┴────────────────────────────┘ Typical road network (OpenStreetMap, London): V \approx 1,000,000 nodes, E \approx 2,500,000 edges (sparse) Binary heap Dijkstra: ~50-100ms on modern CPU for SSSP Space complexity: O(V + E)

4. A* Search and Heuristics

A* (Hart, Nilsson, Raphael 1968) improves Dijkstra by focusing the search toward the goal using a heuristic h(v) — an estimate of the remaining cost from v to the goal t:

A* evaluation function: f(v) = g(v) + h(v) g(v) = exact cost from source s to v (same as d[v] in Dijkstra) h(v) = heuristic estimate of cost from v to goal t A* Algorithm: Same as Dijkstra, but sort priority queue by f(v) = g(v) + h(v) instead of g(v) alone. EXTRACT-MIN returns vertex with smallest f = g + h. Typical heuristics for geometric graphs: Euclidean distance: h(v) = \sqrt((x_v-x_t)² + (y_v-y_t)²) Manhattan distance: h(v) = |x_v-x_t| + |y_v-y_t| (grid graphs) Haversine distance: great-circle distance on sphere (GPS coordinates) Why h helps: Dijkstra explores in concentric circles around source. A* explores an ellipse toward the goal \to fewer nodes expanded. Speedup on road networks: 5-100\times fewer nodes processed than Dijkstra.

5. Admissibility & Consistency

Admissibility (optimality guarantee): h(v) \leq h*(v) for all v h*(v) = true minimum cost from v to goal. "Never overestimate" \to A* still finds optimal path. Consistency (monotone) — stronger condition: h(u) \leq w(u,v) + h(v) (triangle inequality for h) If h is consistent \to g[v] is final when v is first extracted \to no re-insertion needed \to cleaner algorithm Examples: Euclidean distance: consistent ✓ (triangle inequality holds in ℝⁿ) Manhattan on grid: consistent ✓ "Always 0": admissible ✓ \to A* becomes Dijkstra "Direct distance \times 1.5": NOT admissible \to may miss optimal path Inadmissible heuristics (e.g., weighted A* with w > 1): f = g + w\cdoth, w = 1.5 Faster but solution length \leq (1+ε) \times optimal Used in real-time game AI where speed > exactness

6. Algorithm Variants

Bidirectional Dijkstra/A*: Search simultaneously from both source and target. Meets in the middle. Theoretical speedup: search frontier halves. Used in mapping applications. Bidirectional A* requires care with termination condition.
D* Lite: Incremental replanning for robots navigating partially known environments. Efficiently re-computes path when map changes — used in Mars rover navigation.
Jump Point Search (JPS): For uniform-cost grid graphs, JPS recursively identifies "jump points" — pruning vast numbers of intermediate nodes. 10–100× speedup over A* on grids with no preprocessing.
Contraction Hierarchies (CH): Offline preprocessing adds "shortcut" edges. Query time for 1000 km route on European road network: <1ms vs ~50ms for Dijkstra.
HLD-based algorithms (Highway Hierarchies): Exploit the observation that long routes mostly use highways. Conceptual basis for many production GPS systems.
Bellman-Ford: Handles negative weights. O(VE). Underpins OSPF/RIP routing protocols and SPFA (queue-optimised Bellman-Ford).

7. Real-World Applications

GPS Navigation: Google Maps, Apple Maps, and Waze use highly engineered variants of CH + Dijkstra, updated with real-time traffic data. The actual road graph for a continent has ~100M nodes. Preprocessing can take minutes; queries take milliseconds.
Game Pathfinding: NPCs and units in real-time strategy games use A* on navigation meshes (NavMesh) — polygon-based rather than grids. Games like StarCraft 2 run thousands of A* queries per second. JPS is popular for grid-based games.
Network Routing (OSPF): Internet routers run Dijkstra on the link-state database to compute routing tables. Each router has a full map of the network; Dijkstra finds shortest paths to all other routers.
Robotics & Autonomous Vehicles: ROS (Robot Operating System) uses A* and Dijkstra via the `move_base` navigation stack. Self-driving cars combine A* with model-predictive control for trajectory planning.
Airline Scheduling: Finding flight connections, minimum-cost re-routing on cancellations. Multi-criteria shortest path (time + cost + hops).

Computational complexity — P vs NP context: Shortest path in a graph is in P (polynomial time solvable). The hardest related problem, the Travelling Salesman Problem (TSP), is NP-hard — finding the shortest Hamiltonian cycle visiting all nodes. TSP requires visiting each vertex exactly once; shortest path can revisit. This subtle difference transforms a solvable problem into one with no known polynomial-time solution for large inputs.