The one primitive is edge relaxation: for edge (u → v, w), if dist[u] + w < dist[v], we found a cheaper route to v, so update it. Every shortest-path algorithm is "just" a strategy for which order to relax edges. Bellman-Ford's strategy is the simplest possible: relax all of them, V−1 times.
A shortest path in a graph with no negative cycles is simple (no repeated vertices), so it has at most V−1 edges. Hence V−1 passes suffice to propagate every shortest distance to convergence.
Negative-cycle detection. If a V-th relaxation pass still improves some dist[v], then a path with ≥ V edges beats every simple path — impossible unless a reachable negative cycle exists. This is why the extra pass is a detector, not just a formality.
| Algorithm | Time | Neg. edges? | Neg. cycle? | Use when |
|---|---|---|---|---|
| Bellman-Ford | O(V·E) | Yes | Detects | Negative weights present, or bounded-hop paths |
| Dijkstra | O((V+E) log V) | No | — | Non-negative weights (Day 7) |
| 0-1 BFS | O(V + E) | Only 0/1 weights | — | Every edge weight ∈ {0, 1} |
Why it works: the deque holds at most two distinct distance values at any time (d at the front, d+1 at the back). Front-insertion for 0-edges preserves that monotonicity — the same invariant that makes plain BFS correct, extended to a two-level frontier.
Bellman-Ford with negative-cycle detection, then 0-1 BFS on a grid.
import java.util.*;
/** Bellman-Ford. Returns dist[]; null if a negative cycle is reachable. */
public long[] bellmanFord(int n, int[][] edges, int src) {
long[] dist = new long[n];
Arrays.fill(dist, Long.MAX_VALUE);
dist[src] = 0;
for (int pass = 1; pass < n; pass++) { // V-1 passes
for (int[] e : edges) { // relax every edge
int u = e[0], v = e[1], w = e[2];
if (dist[u] != Long.MAX_VALUE && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
}
for (int[] e : edges) { // V-th pass = detector
int u = e[0], v = e[1], w = e[2];
if (dist[u] != Long.MAX_VALUE && dist[u] + w < dist[v])
return null; // negative cycle
}
return dist;
}
/** 0-1 BFS: shortest path when edge weights are all 0 or 1. */
public int zeroOneBfs(List<int[]>[] adj, int n, int src, int dst) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
Deque<Integer> dq = new ArrayDeque<>();
dq.offerFirst(src);
while (!dq.isEmpty()) {
int u = dq.pollFirst();
for (int[] e : adj[u]) {
int v = e[0], w = e[1]; // w is 0 or 1
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0) dq.offerFirst(v); // same layer → front
else dq.offerLast(v); // next layer → back
}
}
}
return dist[dst];
}
dist[u] + w with dist[u] = INT_MAX wraps negative. Guard with the != MAX_VALUE check or use long.dist[v], or you'll process stale entries.src affect the answer; the guard on dist[u] != ∞ handles this.The tell for Bellman-Ford is negative weights, or a hard cap on the number of edges/hops. For 0-1 BFS it's every move costs 0 or 1.
| Disguise / phrasing | What's really asked | Twist to handle |
|---|---|---|
| "Cheapest flight within K stops" | Bounded-hop shortest path | Run exactly K+1 relaxation passes; copy dist each pass |
| "Detect if profit can grow unboundedly" (arbitrage) | Negative-cycle detection | Take logs → negative cycle = arbitrage; V-th pass check |
| "Prices with rebates / negative costs" | SSSP with negative edges | Dijkstra invalid → Bellman-Ford |
| "Free moves vs costly moves" | 0-1 weighted shortest path | Deque: 0-edge push front, 1-edge push back |
| "Min obstacles/walls to remove to reach exit" | 0-1 BFS on a grid | Empty cell = 0, wall = 1 |
| "Min direction changes / rotations" | 0-1 BFS | Same direction = 0, turn = 1 (cf. LC 1368) |