Shortest Paths Overview

The decision tree, before anything else:

unweighted?              -> BFS                       O(V+E)
weights in {0,1}?        -> 0-1 BFS                   O(V+E)
small integer weights?   -> Dial's algorithm          O(VC+E)
acyclic (DAG)?           -> topological DP            O(V+E)   [negatives OK]
non-negative weights?    -> Dijkstra                  O(E log V)
negative weights?        -> Bellman-Ford / SPFA       O(VE)
all pairs, V <= 500?     -> Floyd-Warshall            O(V^3)
all pairs, sparse?       -> Johnson                   O(VE + V^2 log V)
good heuristic available?-> A*

The relaxation invariant

Every shortest-path algorithm is the same operation repeated:

$\text{if }d[u]+w(u,v)<d[v]\text{ then }d[v]\leftarrow d[u]+w(u,v).$

They differ only in the order in which edges are relaxed:

Algorithm	Relaxation order
BFS	by increasing hop count
Dijkstra	by increasing tentative distance (greedy)
DAG DP	topological
Bellman-Ford	all edges, $V-1$ times
SPFA	only vertices whose distance changed
Floyd-Warshall	by allowed intermediate vertex

Properties worth knowing

• Optimal substructure. Any subpath of a shortest path is a shortest path. This is what makes DP and greedy both applicable.
• Shortest path tree. The union of one shortest path to each vertex forms a tree rooted at the source (with consistent tie-breaking).
• At most $V-1$ edges. A shortest path never repeats a vertex when there are no negative cycles — hence Bellman-Ford’s $V-1$ rounds.
• Reweighting. Given potentials $\pi$, replacing $w(u,v)$ by $w(u,v)+\pi (u)-\pi (v)$ changes every $s\to t$ path by the same constant, preserving the shortest path set. This is the trick behind Johnson, Suurballe, and min-cost flow with Dijkstra.

Common variants

Variant	Approach
Path reconstruction	store par[v] on each successful relaxation
Count the number of shortest paths	keep cnt[v]; on < reset, on == add
Second shortest path	keep the best two distinct distances per vertex in the priority queue
Shortest path with exactly $k$ edges	layered graph: state $(v,k)$
Shortest path visiting required vertices	bitmask state $(v,\text{mask})$, $O(2^{k}V\log )$
Minimise the maximum edge (bottleneck)	binary search + BFS, or MST path max, or Dijkstra with max instead of +
Maximise the minimum edge	same, reversed — the MST maximises this
Minimum edges among shortest paths	Dijkstra on the pair (dist, edges)
Shortest path with one edge free / halved	layered graph with one “used the discount” bit
Shortest cycle through a vertex	Dijkstra from it, then check back edges
Shortest even/odd length path	layered graph with a parity bit

The bottleneck path trick

“Minimise the largest edge on the path” is not a sum, but the same greedy works: run Dijkstra with

if (max(dist[u], w) < dist[v]) dist[v] = max(dist[u], w);

Equivalently, the answer is the maximum edge on the path between the two vertices in the minimum spanning tree — a fact worth remembering, because it turns $q$ bottleneck queries into $q$ path-max queries on a tree, answerable with binary lifting in $O(\log V)$ each.

Negative weights: what breaks

Dijkstra assumes that once a vertex is popped its distance is final, which relies on all weights being non-negative. With a negative edge, a later, longer-looking path can improve an already-finalised vertex. The failure is silent — Dijkstra returns a plausible wrong answer rather than crashing. Use Bellman-Ford, or reweight with Johnson first.

See also: Complexity Cheatsheet · Negative Cycles · DAG Shortest Paths