Ultimate Guide: Shortest Path Algorithms
A single source of truth for Dijkstra's Algorithm and A (A-Star).* Written for students, engineers, researchers, and practitioners across Data Structures, AI, ML, and LLM infrastructure. Self-contained — no prior reading assumed. All code is runnable and annotated.
1. Problem Definition & Motivation
1.1 The Shortest Path Problem, Formally
Let $G = (V, E)$ be a graph where:
- $V$ is a finite set of vertices (nodes), $|V| = n$
- $E \subseteq V \times V$ is a set of edges, $|E| = m$
- $w : E \rightarrow \mathbb{R}$ is a weight function assigning a real cost to each edge
A path from $s$ to $t$ is a sequence of vertices $p = \langle v_0, v_1, \dots, v_k \rangle$ where $v_0 = s$, $v_k = t$, and $(v_i, v_{i+1}) \in E$ for all $i$. The weight (cost) of a path is the sum of its edge weights:
$$w(p) = \sum_{i=0}^{k-1} w(v_i, v_{i+1})$$
The shortest-path weight from $s$ to $t$ is defined as:
$$ \delta(s, t) = \begin{cases} \min { w(p) : p \text{ is a path from } s \text{ to } t } & \text{if a path exists} \ \infty & \text{otherwise} \end{cases} $$
A shortest path from $s$ to $t$ is any path $p$ with $w(p) = \delta(s, t)$.
Problem variants:
| Variant | Description | Canonical algorithm |
|---|---|---|
| Single-Source (SSSP) | Shortest paths from one source $s$ to all vertices | Dijkstra, Bellman-Ford |
| Single-Pair | Shortest path from a specific $s$ to a specific $t$ | A*, bidirectional Dijkstra |
| Single-Destination | Shortest paths from all vertices to one target | Dijkstra on reversed graph |
| All-Pairs (APSP) | Shortest paths between every pair | Floyd-Warshall, Johnson's |
⚠️ Note: Dijkstra and A* both solve the non-negative weight shortest path problem. If negative edge weights exist, you need Bellman-Ford (handles negatives, detects negative cycles). We prove why below.
1.2 Why This Matters — Real-World Motivations
Shortest path is one of the most-deployed algorithm families in production software:
- Network routing: OSPF and IS-IS routing protocols run Dijkstra to compute forwarding tables. Every packet on the internet benefits from a shortest-path computation.
- Maps & navigation: Google Maps, Waze, and OSRM use A* and its contraction-hierarchy descendants to route billions of trips.
- Game AI: NPCs and units navigate tile/nav-mesh maps using A* — the single most common pathfinding algorithm in games.
- Robotics & motion planning: Grid- and graph-based planners (A*, Theta*, D* Lite) steer robots and drones.
- NLP & knowledge graphs: Finding the shortest semantic path between two concepts (e.g., WordNet hypernym distance, Wikidata entity linking).
- LLM / RAG pipelines: Graph-based retrieval (GraphRAG) traverses knowledge graphs to assemble multi-hop evidence chains; token-lattice and beam-search decoding are shortest/best-path searches over probability-weighted graphs.
- ML systems: Graph Neural Network message passing, spectral clustering, and manifold learning (Isomap uses shortest paths to approximate geodesic distances in embedding space).
1.3 Classifying Graphs
Choosing the right algorithm starts with correctly classifying your graph:
| Dimension | Types | Implication |
|---|---|---|
| Weighting | Unweighted vs Weighted | Unweighted → BFS is optimal and simpler. Weighted (non-negative) → Dijkstra/A*. |
| Direction | Directed vs Undirected | Undirected edge $(u,v)$ is modeled as two directed edges $u \to v$ and $v \to u$. |
| Weight sign | Non-negative vs Negative | Negatives break Dijkstra's greedy invariant → use Bellman-Ford. |
| Cycles | Cyclic vs Acyclic (DAG) | DAGs allow a simpler $O(V+E)$ topological-sort relaxation. |
| Density | Sparse ($m \approx n$) vs Dense ($m \approx n^2$) | Density dictates the optimal priority-queue / matrix representation. |
⚠️ Note: "Unweighted" is just the special case $w(e) = 1$ for all $e$. On unweighted graphs, BFS already finds shortest paths in $O(V+E)$ — don't reach for Dijkstra there.
2. Prerequisites & Terminology
Before the algorithms, lock down the vocabulary. Every later section builds on these.
Core objects
- Vertex / node: a point in the graph. Edge: a connection with weight $w(u,v)$.
- Neighbor / adjacency: $v$ is a neighbor of $u$ if $(u,v) \in E$. The adjacency list of $u$ is all such $v$ with weights.
- Degree: number of edges incident to a vertex.
Distance labels (the heart of both algorithms)
- $g(v)$ — the best-known cost from the source $s$ to $v$ found so far. Starts at $\infty$ for all $v \neq s$, and $g(s)=0$. It is an upper bound on $\delta(s,v)$ that only decreases.
- $\delta(s,v)$ — the true shortest-path cost (what we're solving for).
- $h(v)$ — (A* only) a heuristic estimate of the remaining cost from $v$ to the goal $t$.
- $f(v) = g(v) + h(v)$ — (A* only) estimated total cost of the cheapest path through $v$.
Key operations
- Relaxation — the fundamental update step shared by all shortest-path algorithms:```text RELAX(u, v, w): if g[u] + w(u, v) < g[v]: g[v] = g[u] + w(u, v) # found a cheaper route to v via u prev[v] = u # remember predecessor for path reconstruction
- **Priority queue (min-heap):** a data structure returning the element with the smallest key in $O(\log n)$. Both algorithms use it to always expand the most promising vertex next.
- **Predecessor map **`prev[]`**:** lets us reconstruct the actual path by walking backward from $t$ to $s$.
**Algorithmic properties**
- **Optimality:** the algorithm returns a path with cost exactly $\delta(s,t)$.
- **Completeness:** if a path exists, the algorithm is guaranteed to find one (and terminate).
- **Admissible heuristic:** $h(v) \le \delta(v, t)$ for all $v$ — *never overestimates* the true remaining cost.
- **Consistent (monotone) heuristic:** $h(u) \le w(u,v) + h(v)$ for every edge, and $h(t)=0$ — the triangle inequality for heuristics.
> ⚠️ **Note:** Consistency $\Rightarrow$ admissibility, but not the reverse. Consistency is the stronger, more useful property — we prove why in §4.2.
3. Dijkstra's Algorithm
Prerequisite check: You need §2's relaxation, distance label $g(v)$, and min-heap concepts. Dijkstra is "greedy relaxation in order of increasing $g$." That single idea drives everything below.
3.1 Intuition & Analogy
Plain English. Dijkstra grows a "settled" region outward from the source. At every step it picks the unsettled vertex with the smallest known distance, declares that distance final, and relaxes its outgoing edges. Because weights are non-negative, once a vertex is picked as the closest remaining one, no cheaper route to it can possibly appear later — so we can lock it in.
Core concept & key insight. The crucial invariant:
When a vertex $u$ is extracted from the priority queue, $g(u) = \delta(s, u)$ — its distance is already optimal and will never change.
Why? Any alternative path to $u$ must leave the settled set through some frontier vertex $x$ with $g(x) \ge g(u)$ (since $u$ was the minimum). Adding the non-negative remaining edges can only increase the cost. Hence no cheaper path exists. This proof breaks the moment an edge weight can be negative — a later negative edge could undercut the "locked" distance. That is precisely why Dijkstra requires $w(e) \ge 0$.
Analogy — Dijkstra as "Cautious Explorer": Imagine exploring a city with unknown road lengths. Dijkstra always walks to the CLOSEST unvisited intersection first, like a cautious traveler who never ventures far until every nearby road is fully mapped. It guarantees the shortest route to every intersection — but because it has no idea where the destination is, it explores outward in ALL directions equally, like ripples spreading on a pond.
Visual / mental model — "uniform wavefront expansion." Picture a circular wave radiating from $s$. The wavefront is the set of vertices currently in the priority queue; the interior is the settled set. The wave advances by always absorbing the nearest frontier vertex. In a uniform-cost grid the settled region looks like a growing diamond/circle centered on $s$ — perfectly symmetric because Dijkstra has no directional bias.
3.2 Algorithm Steps
- Initialize. Set $g(s) = 0$ and $g(v) = \infty$ for every other vertex. Set
prev[v] = Nonefor all $v$. Push $(0, s)$ onto a min-priority-queue keyed by $g$. - Extract-min. Pop the vertex $u$ with the smallest $g$. If it was already settled (stale entry), skip it.
- Settle. Mark $u$ settled; its $g(u)$ is now final ($= \delta(s,u)$).
- Relax neighbors. For each edge $(u, v)$: if $g(u) + w(u,v) < g(v)$, update $g(v)$, set
prev[v] = u, and push $(g(v), v)$. - Repeat steps 2-4 until the queue is empty (SSSP) — or until $t$ is extracted (single-pair early exit).
- Reconstruct the path by following
prev[]backward from $t$ to $s$ and reversing.
3.3 Pseudocode
DIJKSTRA(G, w, s):
for each vertex v in G.V:
g[v] = +infinity
prev[v] = NULL
g[s] = 0
Q = min-priority-queue keyed on g # push all v, or lazily push on relax
Q.insert(s, 0)
while Q not empty:
u = Q.extract-min() # smallest tentative distance
if u is settled: continue # lazy-deletion guard (stale entry)
mark u settled
for each edge (u, v) with weight c = w(u, v):
if g[u] + c < g[v]: # RELAX
g[v] = g[u] + c
prev[v] = u
Q.decrease-key-or-insert(v, g[v])
return (g, prev) # g = distances, prev = shortest-path tree
3.4 Python Implementation
A production-friendly implementation using heapq with lazy deletion (the idiomatic Python pattern — heapq has no decrease-key, so we push duplicates and skip stale pops):
# Dijkstra's Algorithm - annotated Python implementation
import heapq
from typing import Dict, List, Tuple, Hashable
Graph = Dict[Hashable, List[Tuple[Hashable, float]]] # {node: [(neighbor, weight), ...]}
def dijkstra(graph: Graph, start: Hashable):
"""
Single-source shortest paths on a non-negative weighted graph.
graph : adjacency list, {node: [(neighbor, weight), ...]}
start : source node
returns (dist, prev):
dist[v] = shortest distance from start to v (inf if unreachable)
prev[v] = predecessor of v on the shortest path (None if none)
"""
# 1. Initialize every distance to infinity except the source.
dist = {node: float('inf') for node in graph}
prev = {node: None for node in graph}
dist[start] = 0
# settled[] guards against processing a node twice (lazy deletion).
settled = set()
# Min-heap of (tentative_distance, node). Python's heapq is a min-heap.
pq: List[Tuple[float, Hashable]] = [(0, start)]
while pq:
d, u = heapq.heappop(pq) # 2. Extract the closest frontier node.
# 3. Skip stale entries: a better distance was already finalized.
if u in settled:
continue
settled.add(u) # u's distance is now optimal (= delta).
# 4. Relax every outgoing edge of u.
for v, weight in graph[u]:
if v in settled:
continue
new_dist = d + weight
if new_dist < dist[v]: # RELAX: found a cheaper route to v.
dist[v] = new_dist
prev[v] = u
heapq.heappush(pq, (new_dist, v)) # push duplicate; stale one skipped later
return dist, prev
def reconstruct_path(prev: dict, start, target):
"""Walk predecessors backward from target to start, then reverse."""
path, node = [], target
while node is not None:
path.append(node)
if node == start:
break
node = prev[node]
path.reverse()
return path if path and path[0] == start else [] # empty => unreachable
if __name__ == "__main__":
G = {
'A': [('B', 1), ('C', 4)],
'B': [('C', 2), ('D', 5)],
'C': [('D', 1)],
'D': [],
}
dist, prev = dijkstra(G, 'A')
print(dist) # {'A': 0, 'B': 1, 'C': 3, 'D': 4}
print(reconstruct_path(prev, 'A', 'D')) # ['A', 'B', 'C', 'D']
💡 Why lazy deletion instead of decrease-key? Python's
heapqcannot update a key in place. Pushing a fresh(new_dist, v)and skipping outdated pops is simpler and, in practice, faster than maintaining an index fordecrease-key. The heap may hold up to $O(m)$ entries, but each is popped once, so complexity is unchanged (see §3.5).
3.5 Complexity Analysis
Let $n = |V|$ and $m = |E|$. Complexity depends entirely on the priority-queue implementation.
| PQ implementation | extract-min | decrease-key | Total time | When to use |
|---|---|---|---|---|
Binary heap (lazy heapq) | $O(\log n)$ | $O(\log n)$ | $O((n + m)\log n)$ | Default — sparse graphs |
| Fibonacci heap | $O(\log n)$ amort. | $O(1)$ amort. | $O(m + n \log n)$ | Dense graphs, theoretical optimum |
| Array / linear scan | $O(n)$ | $O(1)$ | $O(n^2)$ | Very dense $m \approx n^2$ |
Justification. Each vertex is extracted from the heap exactly once, giving $n$ extract-min operations. Each edge triggers at most one relaxation that may push to the heap, giving up to $m$ pushes. With a binary heap every heap operation is $O(\log n)$ (the heap holds $\le m$ items, and $\log m = O(\log n)$ since $m \le n^2$). Thus $O((n+m)\log n)$, which simplifies to $O(m \log n)$ for a connected graph.
- Best / average / worst time: all $O((n+m)\log n)$ with a binary heap — Dijkstra has no data-dependent early-out (unless you add single-pair early exit), so the bound is tight in every case.
- Space: $O(n)$ for
dist,prev,settled, plus up to $O(m)$ transient heap entries, giving $O(n + m)$ overall.
3.6 Edge Cases & Pitfalls
⚠️ Negative edge weights produce a WRONG ANSWER (not just slowness). Dijkstra settles a node permanently on extraction. A later-discovered negative edge could offer a cheaper route, but the node is already locked. Use Bellman-Ford ($O(nm)$) for negatives; it also detects negative cycles.
- Disconnected / unreachable vertices: their distance stays $\infty$ and
prevstaysNone. Handle this explicitly when reconstructing paths. - Zero-weight edges: perfectly fine (weights need only be $\ge 0$). They don't break the invariant.
- Stale heap entries: must be guarded (the
if u in settled: continuecheck). Forgetting it doesn't corrupt distances but wastes work re-relaxing. - Self-loops & parallel edges: harmless — a self-loop never improves a distance; among parallel edges the min weight wins naturally.
- Floating-point weights: beware accumulated rounding; for exact results prefer integer weights (e.g., store centimeters/milliseconds).
- Single-pair early exit: you may
breakwhen $t$ is extracted (not merely relaxed) — its distance is final only on extraction. Exiting on relaxation is a classic bug.
4. A* Algorithm
Prerequisite check: A* is Dijkstra plus a heuristic. Everything from §3 carries over; the only change is the priority-queue key. Make sure §2's admissibility and consistency definitions are fresh.
4.1 Intuition & Analogy
Plain English. Dijkstra wastes effort exploring away from the goal because it only knows how far it has come ($g$). A* adds an estimate of how far it still has to go ($h$) and prioritizes vertices by the total $f = g + h$. This pulls the search toward the goal, so it typically explores far fewer vertices while still returning the optimal path (given an admissible heuristic).
Core concept & key insight. A* orders the frontier by
$$f(n) = g(n) + h(n)$$
- $g(n)$ = known cost from start to $n$ (exact, same as Dijkstra),
- $h(n)$ = estimated cost from $n$ to goal (the heuristic),
- $f(n)$ = estimated cost of the best full path through $n$.
Setting $h(n) = 0$ everywhere reduces A* to Dijkstra exactly. Making $h$ larger (but still admissible) makes the search more goal-directed and faster. This makes A* a strict, tunable generalization of Dijkstra.
Analogy — A* as "Explorer with a Compass": Same city explorer as before, but now holding a compass and a rough straight-line estimate of the destination's direction. Instead of mapping every nearby road equally, the explorer prefers roads that seem to head toward the goal, only backtracking when a promising road turns into a dead end. Same guaranteed-shortest route, far less walking.
Visual / mental model — "goal-biased teardrop." Where Dijkstra's explored region is a symmetric circle centered on $s$, A*'s explored region is stretched into a teardrop / ellipse pointing from $s$ toward $t$. The stronger (more accurate) the heuristic, the narrower the teardrop — in the ideal case ($h = \delta$) it collapses to a straight beam along the optimal path.
4.2 Heuristic Function $h(n)$ — Admissibility & Consistency
The heuristic is the entire game. Its properties determine correctness and performance.
Admissibility — $h(n) \le \delta(n, t)$ for all $n$ (never overestimates).
- Guarantees optimality for tree-search / graph-search-with-reopening. If $h$ ever overestimates, A* may lock in a suboptimal path and return the wrong answer.
Consistency (monotonicity) — for every edge $(u, v)$: $h(u) \le w(u, v) + h(v)$, and $h(t) = 0$.
- This is the triangle inequality for heuristics. It implies $f$ is non-decreasing along any path.
- Consistency $\Rightarrow$ admissibility (proof: telescope the inequality along the path from $n$ to $t$). The converse is false.
- With a consistent heuristic, the first time A expands a node its $g$ is already optimal* — exactly like Dijkstra — so nodes never need to be reopened. This is why consistency is the property you actually want in production: it makes A* both correct and efficient with a simple closed-set.
⚠️ Note: If your heuristic is admissible but not consistent, you must allow reopening closed nodes (re-adding them to the open set when a cheaper $g$ is found) to preserve optimality. Skipping reopening with an inconsistent heuristic is a subtle, common correctness bug.
Common admissible heuristics on grids/maps:
| Movement model | Heuristic | Formula |
|---|---|---|
| 4-connected grid | Manhattan | $h = |
| 8-connected grid | Octile / Chebyshev | $h = \max(\Delta x, \Delta y) + (\sqrt2 - 1)\min(\Delta x, \Delta y)$ |
| Any-angle / Euclidean | Straight-line | $h = \sqrt{\Delta x^2 + \Delta y^2}$ |
| Roads / arbitrary graph | Great-circle / landmark (ALT) | haversine, or precomputed landmark bounds |
💡 On a 4-connected grid, using the Euclidean distance is still admissible (it never exceeds the Manhattan true cost), but the Manhattan distance is tighter and therefore faster. Prefer the tightest admissible heuristic your movement model allows.
4.3 Algorithm Steps
- Initialize. $g(s) = 0$, $g(v) = \infty$ otherwise. Compute $f(s) = h(s)$. Push $(f(s), s)$ onto the min-heap.
prevallNone. - Extract-min by $f$. Pop the vertex $u$ with the smallest $f$. If already closed, skip.
- Goal test. If $u = t$, reconstruct and return — its path is optimal.
- Close & relax. Mark $u$ closed. For each edge $(u, v)$: tentative $g' = g(u) + w(u,v)$. If $g' < g(v)$, update $g(v)$, set
prev[v] = u, compute $f(v) = g(v) + h(v)$, and push $(f(v), v)$. - Repeat 2-4 until the goal is popped or the queue empties (no path).
4.4 Pseudocode
A-STAR(G, w, s, t, h):
for each vertex v: g[v] = +infinity; prev[v] = NULL
g[s] = 0
open = min-priority-queue keyed on f = g + h
open.insert(s, h(s))
closed = empty set
while open not empty:
u = open.extract-min() # smallest f = g + h
if u == t: return reconstruct(prev, t) # optimal path found
if u in closed: continue
closed.add(u)
for each edge (u, v) with weight c = w(u, v):
g_new = g[u] + c
if g_new < g[v]: # RELAX
g[v] = g_new
prev[v] = u
f_v = g_new + h(v)
open.insert(v, f_v) # (reopen if v was in closed & h inconsistent)
return FAILURE # goal unreachable
4.5 Python Implementation
# A* (A-Star) Algorithm - annotated Python implementation
import heapq
from typing import Dict, List, Tuple, Hashable, Callable
Graph = Dict[Hashable, List[Tuple[Hashable, float]]]
def a_star(graph: Graph, start: Hashable, goal: Hashable,
h: Callable[[Hashable], float]):
"""
Single-pair shortest path with an admissible heuristic h.
graph : adjacency list {node: [(neighbor, weight), ...]}
start : source node
goal : target node
h : heuristic h(node) -> estimated remaining cost to goal (>= 0).
h(node) == 0 for all nodes reduces this to Dijkstra.
returns (path, cost): path as a list of nodes, and its total cost.
Returns ([], inf) if the goal is unreachable.
"""
g = {node: float('inf') for node in graph} # exact cost start -> node
prev = {node: None for node in graph}
g[start] = 0
# Open set: min-heap of (f, g, node). Tie-break on g (prefer larger g,
# i.e. closer to goal) is a common speed trick; here we keep it simple.
open_heap: List[Tuple[float, float, Hashable]] = [(h(start), 0, start)]
closed = set()
while open_heap:
f_u, g_u, u = heapq.heappop(open_heap)
if u == goal: # goal popped => path is optimal
return _reconstruct(prev, start, goal), g_u
if u in closed: # stale / already finalized
continue
closed.add(u)
for v, weight in graph[u]:
tentative_g = g_u + weight
if tentative_g < g[v]: # RELAX
g[v] = tentative_g
prev[v] = u
f_v = tentative_g + h(v) # f = g + h
heapq.heappush(open_heap, (f_v, tentative_g, v))
return [], float('inf') # goal unreachable
def _reconstruct(prev, start, goal):
path, node = [], goal
while node is not None:
path.append(node)
if node == start:
break
node = prev[node]
path.reverse()
return path if path and path[0] == start else []
if __name__ == "__main__":
# Grid coordinates for a Euclidean (admissible) heuristic.
coords = {'A': (0, 0), 'B': (1, 0), 'C': (2, 0), 'D': (2, 1)}
G = {
'A': [('B', 1), ('C', 4)],
'B': [('C', 2), ('D', 5)],
'C': [('D', 1)],
'D': [],
}
def heuristic(n, goal='D'):
(x1, y1), (x2, y2) = coords[n], coords[goal]
return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 # straight-line distance
path, cost = a_star(G, 'A', 'D', heuristic)
print(path, cost) # ['A', 'B', 'C', 'D'] 4
💡 Tie-breaking matters. When multiple nodes share the same $f$, breaking ties toward larger $g$ (nearer the goal) noticeably reduces expansions on grids. Adding a tiny deterministic tie-break like $f \mathrel{+}= h \times \epsilon$ (weighted A*, with tiny $\epsilon$) reduces "plateau" exploration where many cells have equal $f$.
4.6 Complexity Analysis
Let $b$ be the branching factor and $d$ the optimal solution depth.
- Worst-case time: $O(b^d)$ — exponential when the heuristic is uninformative ($h = 0$, i.e. degenerates to Dijkstra/BFS). In graph terms it is the same $O((n+m)\log n)$ as Dijkstra, since every node/edge may still be processed.
- Best case: with a perfect heuristic ($h = \delta$), A* expands only the $d$ nodes on the optimal path — effectively $O(d)$ expansions (plus their neighbors). Linear.
- Average case: strongly heuristic-dependent. The number of expanded nodes is governed by the heuristic's error $|h(n) - \delta(n,t)|$. A* with error bounded by a constant expands a number of nodes polynomial in $d$; with logarithmically-bounded relative error it stays near-linear.
- Space: $O(b^d)$ in the worst case — A* keeps the entire open + closed set in memory. This memory cost is A's Achilles' heel* and motivates IDA* / SMA* (see §8).
Dominance theorem. If $h_2(n) \ge h_1(n)$ for all $n$ (both admissible), then A* with $h_2$ never expands more nodes than with $h_1$ (up to tie-breaking). Tighter admissible heuristics are strictly better.
4.7 Edge Cases & Pitfalls
⚠️ Inadmissible heuristic → loss of optimality. If $h$ overestimates, A* may return a suboptimal path. This is the single most common A* bug. If you intentionally trade optimality for speed, that is Weighted A* ($f = g + \varepsilon h$, $\varepsilon > 1$) — bounded-suboptimal, at most $\varepsilon$ times the optimal cost.
- Inconsistent (but admissible) heuristic: requires node reopening to stay optimal. Forgetting to reopen is a silent correctness bug.
- $h = 0$: correct but wasteful — you have merely re-implemented Dijkstra with extra overhead.
- Heuristic doesn't match the cost metric: e.g., using straight-line distance when edges are travel time with speed limits. $h$ must be a lower bound on the same units as edge weights, or admissibility fails.
- Unreachable goal: the open set empties and A* must return failure — don't loop forever.
- Floating-point $f$ ties / instability: near-equal $f$ values plus float noise cause erratic expansion order; use integer costs or an explicit tie-break key.
- Overly heavy heuristic: if computing $h$ is expensive, a "faster" search can be slower wall-clock. Precompute (landmarks/ALT) or cache.
5. Dijkstra vs A* — Full Comparison
| Criterion | Dijkstra | A* |
|---|---|---|
| Priority key | $g(n)$ | $f(n) = g(n) + h(n)$ |
| Heuristic | None | Yes — domain knowledge via $h(n)$ |
| Goal-directed? | No (explores all directions) | Yes (biased toward goal) |
| Optimal? | Yes (for $w \ge 0$) | Yes, iff $h$ is admissible |
| Complete? | Yes (finite graph) | Yes (finite graph) |
| Time (graph) | $O((n+m)\log n)$ | $O((n+m)\log n)$ worst; far fewer expansions in practice |
| Time (search-tree) | — | $O(b^d)$ worst, $\to O(d)$ with perfect $h$ |
| Space | $O(n+m)$ | $O(n+m)$; worst-case $O(b^d)$ open set |
| Best for | SSSP (one-to-all), unknown/many targets | Single-pair with a good heuristic |
| Special case | A* with $h \equiv 0$ | Generalizes Dijkstra |
| Typical domain | Network routing (OSPF), all-pairs prep | Maps, games, robotics, single-pair |
5.1 When to Use Which
- Use Dijkstra when: you need distances from one source to many/all destinations; you have no usable heuristic; the graph is abstract with no spatial/metric structure (e.g., dependency graphs).
- Use A when:* you have a single (or few) target(s) and a cheap, admissible heuristic (spatial coordinates, landmark bounds). A* is essentially always the win for point-to-point pathfinding on maps/grids.
- Use neither — use BFS when: the graph is unweighted (all $w = 1$). BFS is $O(n+m)$ with no heap overhead.
- Use Bellman-Ford when: negative edges exist (Dijkstra/A* are incorrect here).
💡 Rule of thumb: Dijkstra is A wearing a blindfold.* Give it a compass (admissible $h$) and it becomes A*. If a good compass exists, use it.
5.2 Failure & Edge Cases Side-by-Side
| Situation | Dijkstra | A* |
|---|---|---|
| Negative edges | ❌ Wrong answer → use Bellman-Ford | ❌ Wrong answer → use Bellman-Ford |
| Overestimating heuristic | N/A | ❌ Suboptimal path |
| Inconsistent (admissible) heuristic | N/A | ⚠️ Needs node reopening |
| Unreachable target | ✅ dist = ∞ | ✅ Return failure (open set empties) |
| Huge state space | ✅ $O(n+m)$ memory | ⚠️ Open set can blow up → IDA*/SMA* |
| Many targets at once | ✅ Natural fit | ⚠️ Heuristic aims at one goal |
6. Domain Applications (DS / AI / ML / LLM)
6.1 Data Structures (DS)
- Priority queues & heaps are the beating heart of both algorithms. Binary heaps give the practical $O((n+m)\log n)$; Fibonacci heaps give the theoretical $O(m + n\log n)$ via $O(1)$ amortized decrease-key; d-ary heaps tune the branching factor for cache performance on dense graphs.
- Adjacency list vs. matrix: lists ($O(n+m)$ space) suit sparse graphs; matrices ($O(n^2)$) suit dense graphs and enable the array-based $O(n^2)$ Dijkstra.
- Graph traversal foundation: Dijkstra generalizes BFS (uniform weights) and shares the relaxation core with Bellman-Ford and DAG-shortest-path. Understanding it unlocks the entire shortest-path family.
- Union-Find / MST cousins: Prim's MST algorithm is structurally identical to Dijkstra (swap "distance from source" for "distance from tree") — same heap machinery.
6.2 Artificial Intelligence (AI)
- State-space search: A* is the canonical informed search. Nodes = states, edges = actions with costs, $h$ = admissible estimate to goal (e.g., misplaced-tiles or Manhattan for the 15-puzzle).
- Game AI / pathfinding: A* on tile grids and navigation meshes is the industry-standard NPC movement algorithm. Jump Point Search (§8) accelerates it on uniform grids by orders of magnitude.
- Planning: classical planners (e.g., Fast-Downward) run A* with domain-independent heuristics (landmark, delete-relaxation $h^{max}/h^{add}/h^{FF}$).
- Adversarial & heuristic search connection: the $g+h$ evaluation idea generalizes to branch-and-bound and informed tree search across AI.
6.3 Machine Learning (ML)
- Graph Neural Networks (GNNs): shortest-path distance is a powerful structural feature. Distance encoding and shortest-path-based positional encodings (e.g., in Graphormer) inject topology that vanilla message passing misses. Message passing itself is a bounded-hop relaxation, echoing BFS/Dijkstra layers.
- Manifold learning: Isomap builds a k-NN graph and runs shortest paths (Dijkstra/Floyd-Warshall) to approximate geodesic distances on the data manifold before MDS embedding.
- Clustering: shortest-path / commute-time distances feed spectral and density-based clustering; graph diffusion distances relate to path ensembles.
- Embedding spaces: k-NN graphs over embeddings + shortest path give semantic "how far apart are these two items really" measures that respect the manifold, not just raw cosine distance.
6.4 Large Language Models (LLM)
- Knowledge-graph RAG (GraphRAG): multi-hop question answering traverses an entity–relation graph to assemble an evidence chain. Weighting edges by relation confidence / embedding similarity and running a Dijkstra/A*-style search yields the most-relevant reasoning path between query entities. A* shines here when you have an embedding-similarity heuristic pointing toward the answer entity.
- Retrieval graph navigation: in retrieval pipelines, documents/chunks form a similarity graph; shortest/best-path search connects a query to supporting passages across hops, enabling connected-evidence retrieval instead of isolated top-k.
- Token / decoding lattices: beam search is best-first search over a graph whose edges carry $-\log P(\text{token})$ weights. Minimizing summed negative-log-probability is literally a shortest-path problem over the token lattice; constrained decoding adds edge feasibility. A*-style admissible future-cost estimates power A decoding* for lookahead-guided generation.
- Agent/tool planning: an LLM agent choosing a sequence of tool calls to reach a goal state is doing state-space search; A* with an LLM-estimated heuristic $h$ (cost-to-go) prunes the action tree.
💡 Unifying lens for LLM folks: any time you minimize a sum of non-negative edge costs to connect a start to a goal — probabilities via $-\log$, embedding distances, relation confidences — you are running Dijkstra. Add a cost-to-go estimate and it's A*.
7. Expert Takeaways & Production Tips
Interview insights & gotchas
- Dijkstra fails on negative edges — the #1 interview trap. Know why (the settle-on-extract invariant) not just that.
- Python
heapqhas no decrease-key → use lazy deletion (push duplicate, skip stale on pop). Interviewers love this. - A* is optimal iff $h$ is admissible; consistent heuristics additionally avoid reopening. Be able to state both.
- Early exit for single-pair Dijkstra fires on extraction of $t$, not relaxation.
- BFS = Dijkstra with unit weights; Prim's MST = Dijkstra with a different key. Show the connections.
Production optimization tricks
- Bidirectional search: run two Dijkstra/A* frontiers from $s$ and $t$; meet in the middle → roughly halves the explored radius (§8).
- Contraction Hierarchies (CH) and ALT (A, Landmarks, Triangle-inequality):* preprocessing that makes continental road-network queries microsecond-fast — how real map engines work.
- Tighter heuristics dominate: by the dominance theorem, invest in a better admissible $h$ before micro-optimizing the loop.
- Integer costs: avoid float drift; enable radix/bucket heaps (Dial's algorithm, $O(m + nC)$ for small integer max-weight $C$).
- Cache-friendly graph layout: CSR (compressed sparse row) adjacency +
d-ary heap beats pointer-chasing adjacency lists on large graphs. - Goal-directed pruning + reach/arc-flags for repeated queries on a static graph.
Pitfalls to avoid in implementation
- Reconstructing a path without checking reachability (returns garbage for $\infty$ nodes).
- Relax-then-early-exit bug in single-pair Dijkstra.
- Forgetting the stale-entry guard (correct but slow) — or worse, mutating heap entries in place.
- Mismatched heuristic units vs. edge-cost units (breaks admissibility silently).
- Using Dijkstra on unweighted graphs (BFS is simpler and faster).
8. Advanced Extensions
- Bidirectional Dijkstra / A:* search forward from $s$ and backward from $t$ simultaneously; stop when frontiers meet. Explored volume shrinks from one big ball to two small ones — often a large constant-factor speedup. Correct termination condition is subtle (must account for the meeting-node's combined distance).
- IDA (Iterative-Deepening A):** depth-first search bounded by an increasing $f$ threshold. Uses $O(d)$ memory instead of A*'s exponential open set — the standard fix for memory-bound puzzle search.
- SMA (Simplified Memory-Bounded A):** A* that drops the highest-$f$ leaves when memory fills, remembering their cost in the parent so it can regenerate them — optimal within the memory it's given.
- D / D Lite / LPA*:** incremental replanning for dynamic graphs where edge costs change (robot discovers an obstacle). Reuses previous search effort instead of replanning from scratch — used in real robots and the Mars rovers' lineage.
- Theta (any-angle pathfinding):* relaxes the grid constraint by allowing line-of-sight parent shortcuts, producing shorter, more natural paths than grid-locked A*.
- Jump Point Search (JPS): on uniform-cost grids, skips over symmetric "in-between" cells by jumping to decision points — often 10x+ faster than vanilla A* with identical optimal results.
- Contraction Hierarchies (CH) / Hub Labeling: heavy preprocessing that answers point-to-point road queries in microseconds; the technology behind modern web map routing.
- Dial's algorithm & radix heaps: bucket-based priority queues giving near-linear Dijkstra for small integer edge weights.
- Delta-stepping: a parallelizable Dijkstra variant that buckets vertices by distance ranges — the basis of many GPU/distributed SSSP implementations.
9. Cheat Sheet & Quick Reference
9.1 Formulas to Memorize
| Concept | Formula |
|---|---|
| Path cost | $w(p) = \sum_{i} w(v_i, v_{i+1})$ |
| Shortest-path weight | $\delta(s,t) = \min { w(p) : p : s \rightsquigarrow t }$ |
| Relaxation | if $g(u) + w(u,v) < g(v)$: $g(v) \gets g(u) + w(u,v)$ |
| A* evaluation | $f(n) = g(n) + h(n)$ |
| Admissibility | $h(n) \le \delta(n, t)$ |
| Consistency | $h(u) \le w(u,v) + h(v)$, $h(t)=0$ |
| Dijkstra time (binary heap) | $O((n+m)\log n)$ |
| Dijkstra time (Fibonacci) | $O(m + n \log n)$ |
| A* time (worst, tree) | $O(b^d)$ |
| Weighted A* bound | cost $\le \varepsilon \cdot$ optimal, $\varepsilon > 1$ |
9.2 Decision Flowchart — "Which Algorithm Should I Use?"
START: shortest path needed
|
Are any edge weights negative?
/ \
YES NO
| |
Bellman-Ford Are all weights equal (unweighted)?
(detects neg cycles) / \
YES NO
| |
BFS Do you have a cheap,
(O(n+m)) admissible heuristic
AND a single target?
/ \
YES NO
| |
A* Need one-to-ALL
(goal-directed) or many targets?
/ \
YES NO/few
| |
Dijkstra Dijkstra
(SSSP) + early exit
(or A* if h exists)
(Huge state space + memory-bound? -> IDA* / SMA*)
(Dynamic edge costs / replanning? -> D* Lite / LPA*)
(Continental road network, repeated queries? -> CH / ALT)
9.3 One-Page Recap
- Both algorithms = "relax edges in a smart order using a min-heap." Require $w \ge 0$.
- Dijkstra: order by $g$ (cost so far). One-to-all. No heuristic. Blindfolded — explores a symmetric ball.
- A:* order by $f = g + h$. Point-to-point. Needs admissible $h$. Compass — explores a goal-biased teardrop.
- $h \equiv 0 \Rightarrow$ A = Dijkstra.* Tighter admissible $h \Rightarrow$ fewer expansions (dominance theorem).
- Optimality: Dijkstra always (for $w\ge0$); A* iff $h$ admissible. Consistency avoids node reopening.
- Complexity: both $O((n+m)\log n)$ with a binary heap; A* usually explores far fewer nodes in practice.
- Break glass: negatives → Bellman-Ford; unweighted → BFS; memory-bound → IDA*/SMA*; dynamic → D* Lite; roads at scale → CH/ALT.
✅ The one sentence to remember: Dijkstra guarantees the shortest path by exploring everything nearby first; A guarantees the same shortest path but uses a heuristic compass to explore mostly toward the goal — and A* is exactly Dijkstra when that compass says nothing.*
Related Guides
Prerequisites: Graph Theory · Heaps & Priority Queues
See also: Graph Theory · Greedy Algorithms & Interval Scheduling · Beam Search & Constrained Decoding
Section: Advanced DSA · All guides