Three shortest-path algorithms, one plant network
Dijkstra when every lane costs something. Bellman-Ford when some lanes pay you back. Floyd-Warshall when you need every pair at once. Same nine nodes, same edge weights — watch each one work and see exactly where the other two would have been wrong or wasteful.
The network: eight corrugated plants around Chicago and one distribution center, directed lanes with transit time in minutes. This is the graph under a transshipment model — the one in transportation-and-transshipment-models — before you add capacities and turn it into a flow problem.
Which one, when
| Algorithm | Answers | Edge weights | Cost | Use it for |
|---|---|---|---|---|
| Dijkstra | one source → all | non-negative only | O((V+E) log V) | Routing, ETAs, "nearest plant that can make this grade." The default. |
| Bellman-Ford | one source → all | any; detects negative cycles | O(V·E) | Backhaul credits, currency/arbitrage, anything where an edge can reduce cost. Slower, but honest. |
| Floyd-Warshall | every pair | any; detects negative cycles | O(V³) | Distance matrices for a solver (transshipment, TSP, facility location). Dense graphs up to a few hundred nodes. |
| BFS | one source → all | all equal (hops) | O(V+E) | Unweighted: fewest handoffs, fewest stages. Dijkstra with the queue swapped for a plain one. |
The decision is really two questions: can a weight be negative? and do I need one source or all of them? Dijkstra is fastest and most people's default, but it has a precondition, and the second visual below shows it quietly returning a wrong answer when that precondition fails.
1 · Dijkstra: greedy, and correct because weights are non-negative
Keep a tentative distance for every node, starting at 0 for the source and ∞ elsewhere. Repeatedly pull the unsettled node with the smallest tentative distance, mark it settled, and relax each outgoing edge: if going through this node is shorter than what the neighbor had, update it. CLRS §24.3; Kleinberg–Tardos §4.4 proves it with the same exchange argument as every other greedy in chapter 4; Abdul Bari's lecture 45.
The greedy step is "the smallest unsettled node is final." That's true only because every edge is ≥ 0: nothing you discover later can make a settled node cheaper. Settle a node once, never revisit it — that's where the speed comes from, and it's exactly the assumption the next section breaks.
2 · Bellman-Ford: slower, and the only one that survives a negative edge
Suppose the Naperville → Aurora lane has a backhaul credit: a carrier is paying to move an empty trailer that direction, so running it costs you −20 instead of +24. Dijkstra settles Aurora at 76 via Elgin, before it has even reached Naperville at 82 — and once settled, never looks back. The true cheapest route to Aurora goes through Naperville at 62, and every node downstream of Aurora inherits the error. Bellman-Ford doesn't settle anything. It just relaxes every edge, V−1 times, and the right answer propagates:
Why V−1 passes: a shortest path has at most V−1 edges, and each pass is guaranteed to finalize at least one more edge of every shortest path. If a V-th pass still improves something, there's a negative cycle — a loop you could drive forever and get paid — and the problem has no answer. That check is the whole reason Bellman-Ford exists in arbitrage detection, and why solvers run it on your cost matrix before trusting it. CLRS §24.1, Bari lecture 53.
3 · Floyd-Warshall: every pair, three nested loops
Sometimes you don't want one source; you want the whole distance matrix to feed a transshipment or TSP model. Floyd-Warshall is dynamic programming on the question "what's the shortest i→j path using only intermediate nodes from the first k?" Increase k one node at a time; at each step, every pair asks whether routing through node k helps. CLRS §25.2, Bari lecture 49.
for k in nodes:
for i in nodes:
for j in nodes:
d[i][j] = min(d[i][j], d[i][k] + d[k][j])Each k-step is a pass over the matrix; cells that shrink are the pairs for which node k is a useful waypoint. Watch which k changes the most cells — that's your hub. Negative weights are fine; a negative diagonal entry when it finishes means a negative cycle. It's O(V³), which is 729 operations here and 27 million at 300 nodes — still fine; a million nodes is not. For sparse graphs that size, run Dijkstra from each source instead (or Johnson's algorithm if weights are negative).
Where this sits in the stack
- Transshipment models need a cost for every source→sink pair through intermediates. Floyd-Warshall produces that matrix; the LP then decides flows on it. Same with the product-mix style models once there's more than one site.
- Routing and ETAs in a TMS are Dijkstra (or A*, which is Dijkstra with a heuristic to aim it). Non-negative, single-source, fast.
- Backhauls, credits, incentives make weights negative, and then the correct answer and the fast answer diverge. Knowing which algorithm you're actually running is the difference between a plan that's right and a plan that's confidently wrong.
- Critical path from the DAG post is the same relaxation with max instead of min, and only one pass because topological order guarantees predecessors are done. DAGs are the one case where shortest/longest paths are linear time.
The Java
// Dijkstra with a priority queue. Edges non-negative.
static Map<String,Integer> dijkstra(Map<String,List<int[]>> adj, List<String> nodes, String src) {
Map<String,Integer> dist = new HashMap<>();
for (String n : nodes) dist.put(n, Integer.MAX_VALUE);
dist.put(src, 0);
PriorityQueue<Object[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> (int) a[1]));
pq.add(new Object[]{src, 0});
Set<String> settled = new HashSet<>();
while (!pq.isEmpty()) {
Object[] top = pq.poll();
String u = (String) top[0];
if (!settled.add(u)) continue; // stale queue entry
for (int[] e : adj.get(u)) { // e = {toIndex, weight}
String v = nodes.get(e[0]);
if (dist.get(u) + e[1] < dist.get(v)) { // relax
dist.put(v, dist.get(u) + e[1]);
pq.add(new Object[]{v, dist.get(v)});
}
}
}
return dist;
}
// Bellman-Ford. Any weights; returns null on a negative cycle.
static int[] bellmanFord(int n, int[][] edges, int src) { // edges = {u, v, w}
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE / 2);
dist[src] = 0;
for (int pass = 0; pass < n - 1; pass++)
for (int[] e : edges)
if (dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2];
for (int[] e : edges) // pass n: still improving? negative cycle
if (dist[e[0]] + e[2] < dist[e[1]]) return null;
return dist;
}
// Floyd-Warshall. d[i][j] = direct weight, INF if none, 0 on the diagonal.
static void floydWarshall(int[][] d) {
int n = d.length;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
// d[i][i] < 0 for any i ⇒ negative cycle
}