K-stop constraints (Cheapest Flights Within K Stops)
When Dijkstra fails: graph has negative weights
Dense graphs where O(VE) is acceptable
Complexity
Standard BF
O(V · E) time
K-stop variant
O(K · E) time
Space
O(V) for dist array
Neg cycle check
One extra round after V−1
Live Animation · Bellman-Ford · LC #787
Problem
Given 4 cities (nodes 0–3) and flights with costs including a negative-weight edge 1→2(−2), find the shortest distances from city 0. Dijkstra fails with negative weights — Bellman-Ford relaxes all E edges V−1 times, allowing the negative shortcut to propagate correctly.
Input: edges = [[0,1,4],[0,2,5],[1,2,−2],[1,3,6],[2,3,1]], source = 0 · Answer: dist = [0, 4, 2, 3]
Round: INIT
dist[ ] from node 0
Edge Relaxation Table
u→v
w
dist[u]+w
dist[v]
update?
Step 0 / 9
InitRelaxImproved!No UpdateDone
Initialize: dist[0]=0, all others=∞. Will perform V−1=3 relaxation rounds.
Arrays.fill(dist, MAX); dist[src]=0;
Java Pattern Templateskeleton only
// Bellman-Ford — handles negative weights (pattern skeleton)int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0;
for (int i = 0; i < n - 1; i++) { // V−1 roundsfor (int[] e : edges) { // e = [u, v, weight]int u = e[0], v = e[1], w = e[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
}
// Detect negative cycle (optional extra round)for (int[] e : edges)
if (dist[e[0]] + e[2] < dist[e[1]]) { /* negative cycle! */ }
// K-stop variant (LC #787): use previous round's distancesint[] prev = dist.clone(); // freeze prev round to avoid chainingfor (int[] e : edges)
if (prev[e[0]] != MAX && prev[e[0]] + e[2] < dist[e[1]])
dist[e[1]] = prev[e[0]] + e[2]; // only 1-hop from prev