Shortest Path Algorithms

Shortest-path algorithms are the single most-used family of graph algorithms in production code — Google Maps, OSPF (the routing protocol the internet runs on), BGP, A* in every game pathfinder, currency arbitrage, network packet routing. Most of them are variations on one simple idea: relaxation.

What "Relaxation" Actually Is

Maintain a tentative distance \dist[v]\ from the source to every vertex (start at ∞ for everyone except the source, which is 0). For each edge \(u, v, w)\, ask:

> "Can I reach v cheaper by going via u?"

If \dist[u] + w < dist[v]\, update \dist[v] = dist[u] + w\. That's it. Every shortest-path algorithm — Dijkstra, Bellman-Ford, SPFA, A* — is a different *order* in which you do these relaxations.

` relax(u, v, w): if dist[u] + w < dist[v]: dist[v] = dist[u] + w parent[v] = u // for path reconstruction `

Daily Mental Model: Google Maps with Construction

You're at home and want the shortest drive to a friend's place. Google Maps explores nearby roads first, always picking the *cheapest unexplored intersection* to expand next. When it picks an intersection, the cost it has for it is final — that's Dijkstra in one sentence. Now imagine some roads have toll *rebates* (negative weights). Suddenly Dijkstra breaks, because a "settled" intersection might still get cheaper via a rebated road. That's why we need Bellman-Ford.

Beginner Mistakes to Skip

1. Running Dijkstra on a graph with negative edges. It silently returns wrong answers, doesn't even crash. 2. Running BFS on a weighted graph for the shortest path. BFS counts edges, not weights. 3. Running Floyd-Warshall on V = 10⁵. That's 10¹⁵ operations. Floyd-Warshall is for V ≤ ~500. 4. Forgetting to skip stale heap entries in Dijkstra. When you find a better distance to v, you push \(newDist, v)\ without removing the old one. When the stale entry pops later, you must check \if (poppedDist > dist[v]) continue;\. 5. Treating \Infinity + weight\ as a number in fixed-int languages. In Bellman-Ford, if \dist[u] === Infinity\ you must NOT relax — overflow gives nonsense. 6. Forgetting to track parents. \dist\ alone tells you the *length*. To reconstruct the path, store \parent[v] = u\ whenever you relax.

Intermediate: Dijkstra's — The Workhorse

Constraint: non-negative edge weights only.

`js function dijkstra(adj, V, src) { const dist = Array(V).fill(Infinity); dist[src] = 0; const pq = new MinHeap(); // entries: [dist, vertex] pq.push([0, src]); while (pq.size()) { const [d, u] = pq.pop(); if (d > dist[u]) continue; // STALE entry — critical for (const [v, w] of adj[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push([dist[v], v]); } } } return dist; } `

Complexity: O((V + E) log V) with a binary heap. With a Fibonacci heap it's O(E + V log V), but the constants are awful — binary heap wins in practice.

Why it fails on negatives: Dijkstra assumes that once you pop a vertex, its distance is final. A negative edge could make a popped vertex reachable more cheaply later — but Dijkstra never revisits it.

Intermediate: Bellman-Ford — Slower, but Survives Negatives

Constraint: any weights, no negative *cycles*.

`js function bellmanFord(edges, V, src) { const dist = Array(V).fill(Infinity); dist[src] = 0; for (let i = 0; i < V - 1; i++) { // V-1 passes for (const [u, v, w] of edges) { if (dist[u] !== Infinity && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; } } } // Vth pass — if anything still relaxes, there's a negative cycle for (const [u, v, w] of edges) { if (dist[u] + w < dist[v]) return null; } return dist; } `

Why V−1 passes? A shortest path in a graph with V vertices has at most V−1 edges. Each pass guarantees that all paths of length ≤ i are finalised. After V−1 passes, all shortest paths are done.

Why a Vth pass detects a negative cycle? If you can still relax, you must be running through a cycle whose total weight is negative — relaxing infinitely many times.

Complexity: O(V · E). On dense graphs that's O(V³). SPFA (Shortest Path Faster Algorithm) is the queue-optimised variant: only re-process vertices whose distances actually change. Average case much faster, worst case still O(V · E).

Intermediate: Comparison Table

Algorithm	Negative weights	Negative cycles	All pairs	Time	Best for
BFS	n/a (unweighted)	n/a	no	O(V+E)	unweighted shortest path
0-1 BFS	only 0/1 weights	n/a	no	O(V+E)	grids with 0/1 costs
Dijkstra	❌	❌	no	O((V+E) log V)	non-negative weighted SSSP
Bellman-Ford	✅	detects	no	O(V·E)	negatives possible
SPFA	✅	detects	no	avg fast, worst O(V·E)	sparse graphs with negatives
Floyd-Warshall	✅	detects	yes	O(V³)	small dense all-pairs
Johnson's	✅	detects	yes	O(V² log V + VE)	sparse all-pairs
A*	❌	n/a	no	depends on heuristic	goal-directed search

Advanced: Floyd-Warshall — All Pairs in 5 Lines

`js function floydWarshall(W, V) { const d = W.map(row => row.slice()); // copy weight matrix for (let k = 0; k < V; k++) for (let i = 0; i < V; i++) for (let j = 0; j < V; j++) if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j]; return d; } `

The DP recurrence: \d[i][j] using vertices {1..k}\ = min(\d[i][j] using {1..k−1}\, \d[i][k] + d[k][j] using {1..k−1}\). The outer loop must be k. Negative-cycle check: any \d[i][i] < 0\ after the loop signals a negative cycle through vertex i.

Advanced: A* — Dijkstra With a Compass

A* prioritises by \f(n) = g(n) + h(n)\:

• g(n) = actual cost from start to n (same as Dijkstra)
• h(n) = *heuristic* estimate of cost from n to goal

Replace Dijkstra's priority \dist[u]\ with \dist[u] + h(u)\ and you have A*. Same code, dramatically fewer expansions when the heuristic is good.

Heuristic must be admissible — never *overestimates* the true remaining cost. With an admissible heuristic, A* returns the optimal path.

Movement	Admissible heuristic
4-directional grid	Manhattan distance \	x₁−x₂	+	y₁−y₂	\
8-directional grid	Chebyshev distance \max(	x₁−x₂	,	y₁−y₂	)\
Any-angle (free 2D)	Euclidean distance \√((x₁−x₂)² + (y₁−y₂)²)\
Road network	great-circle distance ÷ max road speed

h ≡ 0 turns A* into pure Dijkstra. h = true distance would expand only the optimal path. Real heuristics sit between.

Advanced: Johnson's Algorithm — All-Pairs for Sparse Graphs

Floyd-Warshall is O(V³). On a sparse graph that's wasteful. Johnson's: 1. Add a virtual vertex \s\ connected to every vertex with weight 0. 2. Run Bellman-Ford from \s\ to get \h(v)\ for every v (also detects negative cycles). 3. Reweight every edge \(u, v, w) → w' = w + h(u) − h(v)\. The new weights are guaranteed non-negative. 4. Run Dijkstra from each vertex on the reweighted graph. 5. Convert reweighted distances back: \true_dist(u, v) = d'(u, v) − h(u) + h(v)\.

Complexity: O(V·E + V² log V). Much better than O(V³) when E ≪ V².

Advanced: When to Use Which — The Decision Tree

Problem shape	Algorithm
Unweighted, single source	BFS
0/1 weights only	0-1 BFS with deque
Non-negative weights, single source	Dijkstra
Has negative weights, single source	Bellman-Ford (or SPFA)
Need to detect negative cycle	Bellman-Ford or Floyd-Warshall
All pairs, V ≤ ~500	Floyd-Warshall
All pairs, V large but sparse	Johnson's
Goal-directed, good heuristic available	A*
K-shortest paths	Yen's algorithm (Dijkstra-based)	Advanced: Real-World Applications	Domain	Algorithm
Google / Apple Maps driving directions	A* with road-network heuristics + contraction hierarchies
OSPF (interior routing on the internet)	Dijkstra in every router
RIP (older interior routing)	Distance-vector ≈ Bellman-Ford
BGP (inter-domain routing)	Path-vector, Bellman-Ford-style
Currency arbitrage detection	Bellman-Ford — negative cycle in log(rate) graph = arbitrage opportunity
Game pathfinding (Civ, RTS)	A* with grid heuristics
Network packet routing	Dijkstra at link-state level
Robotics motion planning	A* / D* on configuration space

Practice Path

1. Implement Dijkstra with a min-heap and full path reconstruction via a \parent\ array. Test on a small weighted graph and verify against a manual run. 2. Implement Bellman-Ford and use the V-th-pass trick to detect a negative cycle in a weighted directed graph. 3. Implement A* on a 2D grid with Manhattan distance as the heuristic. Compare the number of expanded cells against pure Dijkstra on the same grid. 4. Run Floyd-Warshall on a small dense graph (V ≤ 100). Verify \d[i][j]\ matches running Dijkstra from each vertex.