templates · Shortest paths & spanning trees

Bellman–Ford

  • Shortest path where some edge weights are negative
  • "At most k stops" or "at most k edges": the number of edges is limited
  • You must detect a negative cycle (a loop that keeps making the path cheaper)

Bellman–Ford

the one rule

The invariant

After r rounds, dist[v] is at most the cheapest cost of reaching v with r edges or fewer. With the copy (k-stops version) it is exactly that cost.

write it from memory

The template

shortest paths + negative cycle check

javajava.util.*
/** Shortest distance from src to every node. edges[i] = {u, v, w}, w may be negative. null = negative cycle. */static long[] shortestFrom(int n, int[][] edges, int src) {    final long INF = Long.MAX_VALUE / 4;              // "not reached yet"; INF + w cannot overflow    long[] dist = new long[n];    Arrays.fill(dist, INF);    dist[src] = 0;    for (int round = 1; round < n; round++) {         // n - 1 rounds are always enough        boolean changed = false;        for (int[] e : edges) {            int u = e[0], v = e[1], w = e[2];            if (dist[u] != INF && dist[u] + w < dist[v]) { // relax u → v                dist[v] = dist[u] + w;                changed = true;            }        }        if (!changed) break;                          // nothing moved: finished early    }    for (int[] e : edges)                             // one extra round: still improving?        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return null;    return dist;}

A shortest simple path has at most V − 1 edges, so V − 1 rounds are enough. If one more round still improves something, a negative cycle is reachable.

fill in the blanks — only these lines change per problem

  1. line 6The source: one node, or several nodes all set to 0 if many start points are allowed.
  2. line 11The relax rule. Change + w if the cost is not a plain sum.
  3. line 19What a negative cycle means for your problem: return null, -1, or mark nodes as "no answer".

at most k stops

javajava.util.*
/** Cheapest price from src to dst with at most k stops (k + 1 flights), or -1. flights[i] = {u, v, price}. */static int cheapestWithinK(int n, int[][] flights, int src, int dst, int k) {    final int INF = Integer.MAX_VALUE;    int[] dist = new int[n];    Arrays.fill(dist, INF);    dist[src] = 0;    for (int round = 0; round <= k; round++) {        // round r allows r + 1 flights        int[] next = dist.clone();                    // read old, write new: one more edge per round        for (int[] f : flights) {            int u = f[0], v = f[1], w = f[2];            if (dist[u] != INF && dist[u] + w < next[v]) next[v] = dist[u] + w;        }        dist = next;    }    return dist[dst] == INF ? -1 : dist[dst];}

Read from last round's dist, write into a copy. Then each round adds exactly one more edge, which is what "k stops" needs.

fill in the blanks — only these lines change per problem

  1. line 7How many edges are allowed: k stops = k + 1 flights = k + 1 rounds.
  2. line 8Keep this copy. Without it, one round can chain several edges and break the limit.
  3. line 15What to return when dst is never reached.

complexity

What it costs

time O(V · E)
Up to V − 1 rounds, and each round relaxes all E edges once. The early exit helps when nothing changes.
space O(V)
One distance per node (two arrays in the k-stops version: last round and this round).

watch out

Common bugs

  • Updating dist in place in the k-stops version. Then a single round can use many edges, and the answer ignores k.
  • Adding to INF without a guard. Check dist[u] != INF first, or INF + w overflows and turns negative.
  • Forgetting the extra round, so a negative cycle is never caught.

use it

Practise it on

learn it properly