Chapter 7. The Shortest Path Problem

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

This page: LLP forms. View classical forms »

The LLP perspective

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

• LLP-Dijkstra. Forbidden: $j$ is non-fixed and reachable ($d[j] < \infty$). A setPriority(G[j], min) schedule always advances the non-fixed vertex of smallest $d[j]$ next — exactly the Dijkstra-extract step — so the min-heap is part of the schedule, not the predicate. Advance: fix $j$ and relax its outgoing edges.
• LLP-BellmanFord. Forbidden: some edge $(u, v)$ has $G[v] > G[u] + w(u, v)$. Advance: $G[v] := G[u] + w(u, v)$. Lattice-linear because lowering $G[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.

All four ship as runnable LL programs below, each with a full step-through demo.

LLP-Dijkstra

LLP form of Dijkstra. Forbidden: $j$ is non-fixed and reachable ($G[j] < \infty$). Unlike LLP-BellmanFord, this program carries a setMode(PriorityQueue) / setPriority(G[j], min) schedule, so advance always picks the non-fixed vertex of smallest $G[j]$ — exactly Dijkstra's extract-min step — fixing it and relaxing its outgoing edges, tightening $G[k]$ for every non-fixed neighbor $k$. The demo below realizes that schedule as a linear scan for the smallest-$G[j]$ forbidden vertex, since there is no real decrease-key heap in the browser runtime; the compiled Java (see the src-links below) uses an actual PriorityQueue.

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.

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: $G[i] + w(i, j) < G[j]$; the advance lowers $G[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.

LLP-FloydWarshall

Lifts the FloydWarshall recurrence to a lattice-linear program on the full $n \times n$ distance matrix $G$. Index $(i, j)$ is forbidden when some intermediate vertex $k$ improves it: $G[i, j] > G[i, k] + G[k, j]$; the advance sets $G[i, j]$ to the minimum such triangle sum over all $k$.

Time complexity: $O(n^3)$, matching classical FloydWarshall.

LLP-Johnson

Computes a non-negative price vector $G$ that, after reweighting each edge by $w'(i, j) = w(i, j) + G[j] - G[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 maximized, distances are minimized).

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.

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 8 (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.