Chapter 8. The Shortest Path Problem

Single-source and all-pairs distances via greedy fixing, edge relaxation, and reweighting.

This page: LLP forms. View classical forms »

Setting

Given a weighted directed graph $(V, E, w)$ with $n = |V|$ and $m = |E|$, the single-source shortest-path (SSSP) problem asks, for a designated source $v_0$ and every vertex $x$, the minimum total weight $\text{cost}[x]$ of any directed $v_0 \to x$ path. The all-pairs shortest-path (APSP) problem asks the $n \times n$ matrix of shortest-path distances between every pair of vertices.

Dijkstra's Algorithm

For graphs with non-negative edge weights, the greedy idea works: among the vertices not yet finalised, the one with the smallest tentative distance must be at its true shortest distance. Dijkstra repeatedly extracts that vertex (using a min-heap keyed on the tentative distance), fixes it, and relaxes its outgoing edges: $d[k] := \min(d[k], d[j] + w(j, k))$. Sequential running time: $O((n + m) \log n)$ with a binary heap, $O(m + n \log n)$ with a Fibonacci heap. Correctness rests on edge non-negativity: extending any path can only make it longer, so the smallest tentative distance is final.

BellmanFord Algorithm

Removes the non-negativity restriction. BellmanFord performs $n - 1$ passes over every edge, relaxing each. After $i$ passes, $d[x]$ is the shortest-path distance among paths using at most $i$ edges; after $n - 1$ passes, all simple shortest paths have been captured. A final $n$-th pass detects negative cycles: any edge that still relaxes witnesses a negative-weight cycle reachable from the source. Sequential running time: $\Theta(nm)$.

FloydWarshall Algorithm

A clean dynamic-programming APSP algorithm. Let $d^{(k)}[i][j]$ be the shortest-path distance from $i$ to $j$ using only $\{v_1, \ldots, v_k\}$ as intermediate vertices. The recurrence $d^{(k)}[i][j] = \min(d^{(k-1)}[i][j], d^{(k-1)}[i][k] + d^{(k-1)}[k][j])$ fits in a triple loop over $k, i, j$ with $\Theta(n^3)$ total work and $\Theta(n^2)$ space (the $k$ index can be updated in-place). Negative edges are allowed, but no negative cycles.

Johnson's Algorithm

For sparse graphs, FloydWarshall's $\Theta(n^3)$ is wasteful. Johnson's algorithm combines BellmanFord and Dijkstra: first add a virtual source $s^\star$ with zero-weight edges to every vertex and run BellmanFord to compute prices $\text{price}[v] = -\text{dist}(s^\star, v)$. Reweighting each edge $(u, v)$ to $w'(u, v) = w(u, v) + \text{price}[v] - \text{price}[u]$ yields an equivalent graph (same shortest-path structure) with all non-negative weights. Now run Dijkstra from each vertex on the reweighted graph and undo the shift via $D[u, v] = \text{dist}'(u, v) + \text{price}[u] - \text{price}[v]$. Total time: $O(mn + n^2 \log n)$ — faster than $\Theta(n^3)$ when $m = o(n^2 / \log n)$.

Plain text: LL · Java · Python · C++ · Rust

The LLP perspective

All four algorithms admit lattice-linear reformulations on the distance vector $d[1..n]$:

• LLP-Dijkstra. Forbidden: $j$ is non-fixed and its $d[j]$ is the global minimum among non-fixed vertices. Advance: fix $j$ and relax its outgoing edges. The forbidden condition picks out exactly the Dijkstra-extract step; the LLP runtime can use a min-heap to find it in $O(\log n)$.
• LLP-BellmanFord. Forbidden: some edge $(u, v)$ has $d[v] > d[u] + w(u, v)$. Advance: $d[v] := d[u] + w(u, v)$. Lattice-linear because lowering $d[v]$ never invalidates other resolved indices.
• LLP-FloydWarshall. Lifts the recurrence to a 2D distance matrix; the forbidden condition checks the triangle inequality across all pairs.
• LLP-Johnson. Replaces BellmanFord with an LLP-Pricing program to derive the potentials, then runs LLP-Dijkstra from each vertex.

Three of these ship as runnable LL programs below. LLP-Dijkstra is shown as a code listing only (it relies on a priority-queue runtime that is not yet wired into the in-page stepper). LLP-BellmanFord and LLP-Johnson have full step-through demos.

LLP-Dijkstra

LLP form of Dijkstra. The forbidden index is whichever non-fixed vertex currently sits at the head of a priority queue keyed on $d[j]$; advancing it fixes the vertex and (in a full front-end) relaxes its outgoing edges. The setMode(PriorityQueue) clause tells the LL runtime to maintain a min-heap of candidate forbidden indices; setPriority(d[j], min) keys the heap on the current distance.

Time complexity: $O((n + m) \log n)$ with a binary heap, where $n$ is the number of vertices and $m$ is the number of edges.

int[] LLPDijkstra(int[] dIn) {
  int[]     d     = infinity;
  boolean[] fixed = false;

  setMode(PriorityQueue);
  setPriority(d[j], min);

  forbidden (j) : !fixed[j]  =>
    advance : fixed[j] = true;
  return d;
}

LLP-BellmanFord

Single-source shortest paths with possibly-negative edge weights (no negative cycle). Vertex $j$ is forbidden when some predecessor $i$ would relax it: $d[i] + w(i, j) < d[j]$; the advance lowers $d[j]$ to the minimum over all predecessors. Lattice-linear because each lowering is monotone in the surrounding state.

Time complexity: $O(n \cdot m)$, where $n$ is the number of vertices and $m$ is the number of edges.

int[] LLPBellmanFord(set<int>[] pre, int[][] w) {
  int[] d = infinity;
  d[0] = 0;
  forbidden (j) :
    exists i in pre[j] : d[j] > d[i] + w[i][j]
  =>
    advance :
      forall k in [0..n] :
        d[k] = min(d[k], min i in pre[k] : d[i] + w[i][k]);
  return d;
}

LLP-Johnson

Computes a non-negative price vector $p$ that, after reweighting each edge by $w'(i, j) = w(i, j) + p[j] - p[i]$, leaves all weights non-negative — the preprocessing step of Johnson's algorithm. The forbidden / advance pair is the dual of LLP-BellmanFord with $\max$ replacing $\min$ (because prices are maximised, distances are minimised).

Time complexity: $O(n m + n^2 \log n)$ (BellmanFord preprocessing plus $n$ Dijkstra runs), where $n$ is the number of vertices and $m$ is the number of edges.

int[] LLPJohnson(set<int>[] pre, int[][] w) {
  int[] p = 0;
  forbidden (j) :
    exists i in pre[j] : p[j] < p[i] - w[i][j]
  =>
    advance :
      forall k in [0..n] :
        p[k] = max(p[k], max i in pre[k] : p[i] - w[i][k]);
  return p;
}

Constrained shortest path

Two common side conditions on shortest paths are a hop budget (no more than $k$ edges along the chosen path) and a resource budget (the total of a secondary edge cost stays within $B$). Each is expressed as a one-rule constraint program operating on an augmented state vector — $h[j]$ is the hop count along the relaxation chain that established $G[j]$; $\rho[j]$ is the cumulative resource. The Lattice-Linear Language's predicate-conjunction operator $\&\&$ composes the constraint with LLP-Dijkstra.

HopBound

Enforces $h[j] \leq k$. Forbidden when some vertex has more than $k$ hops on its current shortest-path chain. Advance halts ``infeasible'' (returns null), since no further relaxation can shorten the hop count without first improving $G[j]$. Composed with LLP-Dijkstra-Hops: $[\,\textsf{LLP-Dijkstra-Hops}\,\&\&\,\textsf{HopBound}\,]$.

Time complexity: $O((n + m) \log n)$, identical to LLP-Dijkstra up to constant factors.

int[] HopBound(int[] h, int k, int[] G) {
  forbidden (j) : h[j] > k =>
    advance : return null;
  return G;
}

ResourceBound

Enforces $\rho[j] \leq B$. Forbidden when the resource consumption of some vertex's relaxation chain exceeds the budget. Advance halts ``infeasible''. Composed with LLP-Dijkstra-Res: $[\,\textsf{LLP-Dijkstra-Res}\,\&\&\,\textsf{ResourceBound}\,]$. The single-state formulation may miss a feasible path of lower cost; a Pareto-frontier extension is sketched in the textbook and runs in pseudo-polynomial time $O((n + m) B \log n)$ for integer resources.

Time complexity: $O((n + m) \log n)$ for the single-state variant.

int[] ResourceBound(int[] rho, int B, int[] G) {
  forbidden (j) : rho[j] > B =>
    advance : return null;
  return G;
}

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[i]$ represents and the negation of the forbidden clause from the matching .llp source.

Looking ahead

Shortest-path machinery underpins Chapter 9 (minimum spanning trees), where Prim's algorithm shares Dijkstra's "fix-the-closest-frontier-vertex" structure but uses a different relaxation rule. Johnson's reweighting reappears in network-flow chapters as the key idea behind successive-shortest-paths and primal-dual methods. The $\Delta$-stepping algorithm (covered in the book's later sections) bridges LLP-Dijkstra and LLP-BellmanFord via a tunable bucket width.