vi. Shortest Paths

All single-source algorithms repeat one operation, relaxation ($d_v\leftarrow \min (d_v,d_u+w_{uv})$), and differ in the order: by distance (Dijkstra), by layers of a deque (0-1 BFS), by topological order (DAG), or all edges $n-1$ times (Bellman–Ford). All-pairs: Floyd–Warshall $O(n^3)$, or Johnson’s reweighting + $n$ Dijkstras.

Graph	Algorithm	Time
unweighted	BFS	$O(n+m)$
weights in $\{0,1\}$	0-1 BFS (deque)	$O(n+m)$
small integer weights $\le C$	Dial’s buckets (circular, $C+1$ buckets)	$O(m+nC)$
DAG, any weights	relax in topological order	$O(n+m)$
nonnegative weights	Dijkstra with binary heap / dense array	$O(m\log n)$ / $O(n^2)$
negative weights	Bellman–Ford (SPFA is hackable)	$O(nm)$
all pairs, $n\le 500$	Floyd–Warshall	$O(n^3)$
all pairs, sparse, negative edges	Johnson	$O(nm\log n)$

Dijkstra

const ll INF = LLONG_MAX / 4;
vector<ll> dijkstra(const vector<vector<pair<int, ll>>>& g, int s, vector<int>* par = nullptr) {
    vector<ll> d(sz(g), INF); if (par) par->assign(sz(g), -1);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq; d[s] = 0; pq.push({0, s});
    while (sz(pq)) {
        auto [du, u] = pq.top(); pq.pop();
        if (du != d[u]) continue;                           // stale entry
        for (auto [v, w] : g[u]) if (du + w < d[v]) { d[v] = du + w; if (par) (*par)[v] = u; pq.push({d[v], v}); }
    }
    return d;
}

Dense graphs ($m\approx n^2$): pick the unvisited vertex with minimum $d$ by a linear scan, $O(n^2)$ total. Never run Dijkstra with negative edges: it silently returns wrong answers. The union of one shortest path to each vertex (with consistent tie-breaking) forms a shortest-path tree rooted at the source — the structure that makes “which edges can appear on some/every shortest path” questions tree questions.

Proof: a popped vertex has its final distance

Let $S$ be the set of popped (finalised) vertices and suppose $u$ is the first vertex popped with $d_u>\delta (u)$ (true distance). Take a shortest path $s⇝u$ and let $y$ be its first vertex outside $S$, with predecessor $x\in S$. When $x$ was popped, $d_x=\delta (x)$ and the edge $(x,y)$ was relaxed, so $d_y\le \delta (x)+w_{xy}=\delta (y)\le \delta (u)$, using nonnegative weights for the last inequality. Hence $d_y\le \delta (u)<d_u$, so $y$ would be popped before $u$ (and $y\ne u$ since $d_u>\delta (u)\ge d_y$), contradicting the choice of $u$. Each edge is relaxed once and pushes at most one heap entry: $O(m\log m)$.

0-1 BFS and Dial

vector<int> bfs01(const vector<vector<pair<int, int>>>& g, int s) {   // weights 0 or 1
    vector<int> d(sz(g), INT_MAX); deque<int> dq; d[s] = 0; dq.push_back(s);
    while (sz(dq)) {
        int u = dq.front(); dq.pop_front();
        for (auto [v, w] : g[u]) if (d[u] + w < d[v]) { d[v] = d[u] + w; w ? dq.push_back(v) : dq.push_front(v); }
    }
    return d;
}

Uses: grids where some moves are free (break a wall = 1), minimum edge reversals (reverse edge costs 1), minimum direction changes (state = cell × direction), portals/teleports (0 to teleport, 1 for a normal step), minimum characters to insert (0 to match, 1 to insert), connecting cells where some links are free. For weights in $[0,C]$ use $C+1$ circular buckets (Dial), $O(m+nC)$ — worth it only when $C\lesssim \log n$, since beyond that the bucket sweep costs more than Dijkstra’s heap; a radix heap (bucket by the highest differing bit rather than the exact value) gives $O(m+n\log C)$ for integer weights, and is the general version of which Dial and 0-1 BFS’s deque are the small-$C$ special cases.

Proof: the deque stays sorted with at most two values

Invariant: the deque’s labels are nondecreasing from front to back and span at most $\{d,d+1\}$ where $d$ is the front’s label. Popping $u$ (label $d$), a 0-edge gives $v$ label $d$, pushed to the front, and a 1-edge gives $d+1$, pushed to the back; both preserve the invariant. Hence vertices are popped in nondecreasing order of label, exactly as in Dijkstra, so the Dijkstra proof applies; a vertex may be pushed again only when its label strictly decreases, which happens at most once per incoming edge.

Bellman–Ford and negative cycles

vector<ll> bellmanFord(int n, const vector<array<ll, 3>>& E, int s) {   // -INF: arbitrarily small (via a negative cycle)
    vector<ll> d(n, INF); d[s] = 0;
    for (int it = 0; it + 1 < n; it++) for (auto [u, v, w] : E) if (d[u] < INF && d[u] + w < d[v]) d[v] = d[u] + w;
    for (int it = 0; it < n; it++) for (auto [u, v, w] : E) if (d[u] < INF && (d[u] == -INF || d[u] + w < d[v])) d[v] = -INF;
    return d;
}
vector<int> negativeCycle(int n, const vector<array<ll, 3>>& E) {        // any negative cycle (in order), or empty
    vector<ll> d(n, 0); vector<int> par(n, -1); int x = -1;                // d = 0 everywhere: virtual source
    for (int it = 0; it < n; it++) { x = -1; for (auto [u, v, w] : E) if (d[u] + w < d[v]) d[v] = d[u] + w, par[v] = u, x = v; }
    if (x < 0) return {};
    for (int i = 0; i < n; i++) x = par[x];                                // step back n times: now on the cycle
    vector<int> cyc{x}; for (int v = par[x]; v != x; v = par[v]) cyc.push_back(v);
    reverse(all(cyc)); return cyc;
}

“Is the answer at $t$ unbounded” (CSES High Score): $t$ is $-\infty$ iff some vertex on a negative cycle is reachable from $s$ and reaches $t$; the second loop above propagates that. Difference constraints $x_j-x_i\le c$ reduce directly to this: build edge $i\to j$ of weight $c$, add a super-source at weight 0 to everything, and a negative cycle means the system is infeasible (Graph Basics).

SPFA (queue of vertices whose distance changed, skip re-queueing one already waiting) is fast on random graphs but $O(nm)$ on adversarial ones — these are well-known and easy to generate, so don’t submit plain SPFA where $O(nm)$ would TLE. Detect a negative cycle by counting enqueues: if any vertex is enqueued more than $n$ times, one is reachable from $s$. Two heuristics narrow the gap to Dijkstra without fixing the worst case: SLF (small label first — push $v$ to the front of the queue instead of the back when $d_v$ is below the current front’s label, a generalisation of 0-1 BFS’s deque trick) and LLL (large label last — keep rotating the front to the back while its label exceeds the queue’s average); both together is the common “optimised SPFA,” and both remain hackable.

Proof: Bellman–Ford, cycle extraction

After round $k$, $d_v\le$ the length of the shortest walk from $s$ to $v$ with at most $k$ edges (induction: the last edge of such a walk is relaxed in round $k$ after its prefix is correct). Without negative cycles, shortest walks can be taken simple, with at most $n-1$ edges, so $n-1$ rounds suffice and no edge can be relaxed afterwards. Conversely if a negative cycle $C$ is reachable and no edge in $C$ were relaxable, summing $d_v\le d_u+w_{uv}$ around $C$ gives $0\le w(C)<0$: contradiction. So a reachable negative cycle always leaves a relaxable edge, and $-\infty$ propagates to everything it reaches within $n$ more rounds.
Extraction: if round $n$ still relaxes $x$, the parent pointers from $x$ form a walk backwards; following them $n$ times must enter a cycle of the parent graph. Every cycle in the parent graph has negative weight: when the last edge $(u,v)$ of such a cycle was set, all the parent edges satisfied $d_v\ge d_u+w_{uv}$ with strict inequality for the edge just relaxed, and summing around the cycle gives $w(C)<0$.

Floyd–Warshall

void floyd(vector<vector<ll>>& d) {                       // d[i][i] = 0, INF if no edge; -INF marks unbounded pairs
    int n = sz(d);
    for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) if (d[i][k] < INF) for (int j = 0; j < n; j++)
        if (d[k][j] < INF) d[i][j] = min(d[i][j], max(d[i][k] + d[k][j], -INF));
    for (int k = 0; k < n; k++) if (d[k][k] < 0) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
        if (d[i][k] < INF && d[k][j] < INF) d[i][j] = -INF;
}

Path reconstruction: keep nxt[i][j] (first step), updated as nxt[i][j] = nxt[i][k]. Variants: transitive closure ($\vee ,\wedge$, with bitsets $O(n^3/64)$), bottleneck paths ($\max$ of $\min$), counting shortest paths, adding vertices one by one in any order (“answer queries after activating vertex $k$” is exactly the outer loop).

Proof: the $k$-th round allows intermediates $\mathrm{0..}k$

Invariant: after processing $k$, $d_{ij}$ is the shortest path from $i$ to $j$ whose intermediate vertices lie in $\{\mathrm{0..}k\}$ (assuming no negative cycles). A shortest such path either avoids $k$ (already counted) or passes through $k$ once, splitting into $i⇝k$ and $k⇝j$ with intermediates in $\{\mathrm{0..}k-1\}$, both correct by induction. Updating in place is safe because $d_{ik}$ and $d_{kj}$ don’t change during round $k$ (that would need $d_{kk}<0$). With negative cycles, $d_{kk}<0$ exactly for vertices on one, and $i⇝k⇝j$ through such a $k$ is unbounded; clamping at $-\infty$ prevents the exponential decrease from overflowing.

Potentials and Johnson

For any potential $\pi$, the reduced weights $w_{uv}^{\prime }=w_{uv}+{\pi }_u-{\pi }_v$ change every $s⇝t$ path by the same constant ${\pi }_s-{\pi }_t$, so shortest paths are preserved. With $\pi$ = Bellman–Ford distances from a virtual source, every $w^{\prime }\ge 0$ (triangle inequality), and Dijkstra works. Johnson: one Bellman–Ford + $n$ Dijkstras, $O(nm\log n)$. The same trick keeps min-cost flow on Dijkstra (Min-Cost Flow).

Proof: reduced weights

Telescoping: ${\sum }_{e\in P}{w}_e^{\prime }={\sum }_{e\in P}{w}_e+{\pi }_s-{\pi }_t$ for any path $P$ from $s$ to $t$. If ${\pi }_v=\delta (\text{virtual},v)$, the triangle inequality ${\pi }_v\le {\pi }_u+w_{uv}$ gives $w_{uv}^{\prime }\ge 0$.

Variants

Variant	Approach
number of shortest paths	carry counts: reset on strict improvement, add on ties (process in Dijkstra pop order)
shortest-path DAG / edges on some shortest path	$d_s(u)+w+d_t(v)=d_s(t)$ using a forward and a backward run
edges on all shortest paths	in the shortest-path DAG, edges that are bridges between distance layers: count paths from both ends, ${\text{cnt}}_s(u)\cdot {\text{cnt}}_t(v)={\text{cnt}}_s(t)$ (use two moduli)
second shortest walk (may repeat vertices)	keep the two best distinct distances per vertex; a vertex is popped at most twice
$k$ shortest walks	pop each vertex up to $k$ times ($O(km\log )$), or Eppstein (K Shortest)
one edge may be free / halved	state $(v,\text{used})$
bottleneck (minimise the max edge)	Dijkstra with $\max$ instead of $+$, or the MST path maximum — turning $q$ bottleneck queries into $q$ path-max-on-a-tree queries, answerable in $O(\log n)$ each via binary lifting
fewest edges among shortest	compare $(\text{dist},\text{edges})$ pairs
time-dependent edges (FIFO: leaving later never arrives earlier)	Dijkstra with arrival time $f_e(t)$
multiple sources / targets	virtual super-source, or seed the heap with all sources
distances from all vertices to $t$	Dijkstra on the reversed graph

Hidden DAGs

A graph with cycles can still have a DAG hiding inside it:

• Condensation. Contracting the SCCs of any directed graph gives a DAG; longest path there, weighted by component size, answers “largest set of mutually reachable vertices along a path.”
• Layered state. If the state includes a quantity that only increases (steps taken, fuel spent), the state graph is a DAG even when the underlying graph has cycles.
• Monotone grids. A grid where moves are only right/down is a DAG regardless of how the costs look.

Every DP is a DAG shortest path

A DP’s states and transitions form a DAG — “compute in dependency order” is exactly a topological order, and the recurrence is relaxation. This is why a DP with a cyclic dependency needs Dijkstra or Bellman–Ford instead of a plain loop, and it is also the reason LCS, edit distance, and grid-path counting are “DAG DPs in disguise”: the grid or the two-string product is the DAG. See DP on DAGs.