35.05Intermediate / Advanced4 topics12 min1 interactive animation

SPFA and caveats

SPFA is Bellman-Ford with a queue: only vertices whose distance just improved are processed again. It is often fast, but its worst case equals Bellman-Ford's, and adversarial inputs reach it.

Learning goals

Implement SPFA with a queue and an in-queue flag
Name a heuristic that sometimes helps
Build an input that makes SPFA do far more work
Explain why it is not a guaranteed-fast algorithm

Prerequisites

Bellman-FordQueues

In plain Bellman-Ford most edges are examined without effect once the distances have settled. SPFA avoids that waste, and in practice it can be far faster. Knowing exactly when it is not is part of using it responsibly.

35.05.1

Queue-based relaxation

Only a vertex whose distance has just dropped can lower its neighbours, so keep those vertices in a FIFO queue. Take one out, relax its out-edges, and add any head that improved (unless it is already in the queue). Stop when the queue is empty. The abbreviation stands for *Shortest Path Faster Algorithm*.

To handle negative cycles, store how many edges the best path to each vertex has; a path with n edges repeats a vertex, which means a negative cycle is reachable. The second branch of the Bellman-Ford animation shows the queue and stops on such a cycle in the last preset.

Java

1static long[] spfa(int n, List<int[]>[] adj, int s) {            // adj[u] = {v, w}; null on a reachable negative cycle
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n];
4    Arrays.fill(dist, INF);
5    dist[s] = 0;
6    int[] len = new int[n];                                       // edges on the best path found so far
7    boolean[] inQ = new boolean[n];
8    Deque<Integer> q = new ArrayDeque<>();
9    q.add(s);
10    inQ[s] = true;
11    while (!q.isEmpty()) {
12        int u = q.poll();
13        inQ[u] = false;
14        for (int[] e : adj[u]) {
15            if (dist[u] + e[1] >= dist[e[0]]) continue;
16            dist[e[0]] = dist[u] + e[1];
17            len[e[0]] = len[u] + 1;
18            if (len[e[0]] >= n) return null;                      // a path with n edges repeats a vertex
19            if (!inQ[e[0]]) { q.add(e[0]); inQ[e[0]] = true; }
20        }
21    }
22    return dist;
23}

Bellman-Ford and SPFA: shortest paths with negative edges and cycle detection

Interactive · edit the input

directed graph · 5 vertices · 9 edges

d=0

Edge / vertex being processedIn the queueTree edge (on a best path)Edge that still improves: negative cycle

dist[v]

∞1

∞2

∞3

∞4

Setup

dist[0] = 0 and every other distance is unknown (∞). Relaxing an edge u → v with weight w means: if dist[u] + w is smaller than dist[v], use it. A shortest path has at most n - 1 = 4 edges, so n - 1 passes over all edges are enough.

Step 1 / 32

Java

1long[] bellmanFord(int n, int[][] edges, int s) {   // edges: {u, v, w}; null on a reachable negative cycle
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
4    for (int round = 1; round < n; round++) {     // a shortest path has at most n - 1 edges
5        boolean changed = false;
6        for (int[] e : edges)
7            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) { dist[e[1]] = dist[e[0]] + e[2]; changed = true; }
8        if (!changed) break;                      // nothing improved: finished early
9    }
10    for (int[] e : edges)                         // one more pass: any improvement means a negative cycle
11        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return null;
12    return dist;
13}
14long[] spfa(int n, List<int[]>[] adj, int s) {    // adj[u] = {v, w}; null on a reachable negative cycle
15    long INF = Long.MAX_VALUE / 2;
16    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
17    int[] len = new int[n]; boolean[] inQ = new boolean[n];
18    Deque<Integer> q = new ArrayDeque<>(); q.add(s); inQ[s] = true;
19    while (!q.isEmpty()) {
20        int u = q.poll(); inQ[u] = false;
21        for (int[] e : adj[u]) {
22            if (dist[u] + e[1] >= dist[e[0]]) continue;
23            dist[e[0]] = dist[u] + e[1]; len[e[0]] = len[u] + 1;
24            if (len[e[0]] >= n) return null;      // a best path with n edges repeats a vertex
25            if (!inQ[e[0]]) { q.add(e[0]); inQ[e[0]] = true; }
26        }
27    }
28    return dist;
29}

Live state

0 relaxations0 edges examined

source

No condition evaluated on this step

Execution trace (dry run table)Show 32 steps

Step	Line	State	What happens
1	L3	source=0	dist[0] = 0 and every other distance is unknown (∞). Relaxing an edge u → v with weight w means: if dist[u] + w is smaller than dist[v], use it. A shortest path has at most n - 1 = 4 edges, so n - 1 passes over all edges are enough.
2	L7	round=1 u=0 v=1 dist[v]=6	Round 1, 0 → 1: 0 + 6 = 6 is better, so dist[1] = 6.
3	L7	round=1 u=0 v=2 dist[v]=7	Round 1, 0 → 2: 0 + 7 = 7 is better, so dist[2] = 7.
4	L7	round=1 edge=1 → 2 candidate=14	Round 1, 1 → 2: 6 + 8 = 14 is not better than 7: no change.
5	L7	round=1 u=1 v=3 dist[v]=11	Round 1, 1 → 3: 6 + 5 = 11 is better, so dist[3] = 11.
6	L7	round=1 u=1 v=4 dist[v]=2	Round 1, 1 → 4: 6 + -4 = 2 is better, so dist[4] = 2.
7	L7	round=1 u=2 v=3 dist[v]=4	Round 1, 2 → 3: 7 + -3 = 4 is better, so dist[3] = 4.
8	L7	round=1 edge=2 → 4 candidate=16	Round 1, 2 → 4: 7 + 9 = 16 is not better than 2: no change.
9	L7	round=1 u=3 v=1 dist[v]=2	Round 1, 3 → 1: 4 + -2 = 2 is better, so dist[1] = 2.
10	L7	round=1 edge=4 → 3 candidate=9	Round 1, 4 → 3: 2 + 7 = 9 is not better than 4: no change.
11	L9	round=1 dist=[0, 2, 7, 4, 2]	End of round 1: distances [0, 2, 7, 4, 2]. Paths with up to 1 edges are now correct.
12	L7	round=2 edge=0 → 1 candidate=6	Round 2, 0 → 1: 0 + 6 = 6 is not better than 2: no change.
13	L7	round=2 edge=0 → 2 candidate=7	Round 2, 0 → 2: 0 + 7 = 7 is not better than 7: no change.
14	L7	round=2 edge=1 → 2 candidate=10	Round 2, 1 → 2: 2 + 8 = 10 is not better than 7: no change.
15	L7	round=2 edge=1 → 3 candidate=7	Round 2, 1 → 3: 2 + 5 = 7 is not better than 4: no change.
16	L7	round=2 u=1 v=4 dist[v]=-2	Round 2, 1 → 4: 2 + -4 = -2 is better, so dist[4] = -2.
17	L7	round=2 edge=2 → 3 candidate=4	Round 2, 2 → 3: 7 + -3 = 4 is not better than 4: no change.
18	L7	round=2 edge=2 → 4 candidate=16	Round 2, 2 → 4: 7 + 9 = 16 is not better than -2: no change.
19	L7	round=2 edge=3 → 1 candidate=2	Round 2, 3 → 1: 4 + -2 = 2 is not better than 2: no change.
20	L7	round=2 edge=4 → 3 candidate=5	Round 2, 4 → 3: -2 + 7 = 5 is not better than 4: no change.
21	L9	round=2 dist=[0, 2, 7, 4, -2]	End of round 2: distances [0, 2, 7, 4, -2]. Paths with up to 2 edges are now correct.
22	L7	round=3 edge=0 → 1 candidate=6	Round 3, 0 → 1: 0 + 6 = 6 is not better than 2: no change.
23	L7	round=3 edge=0 → 2 candidate=7	Round 3, 0 → 2: 0 + 7 = 7 is not better than 7: no change.
24	L7	round=3 edge=1 → 2 candidate=10	Round 3, 1 → 2: 2 + 8 = 10 is not better than 7: no change.
25	L7	round=3 edge=1 → 3 candidate=7	Round 3, 1 → 3: 2 + 5 = 7 is not better than 4: no change.
26	L7	round=3 edge=1 → 4 candidate=-2	Round 3, 1 → 4: 2 + -4 = -2 is not better than -2: no change.
27	L7	round=3 edge=2 → 3 candidate=4	Round 3, 2 → 3: 7 + -3 = 4 is not better than 4: no change.
28	L7	round=3 edge=2 → 4 candidate=16	Round 3, 2 → 4: 7 + 9 = 16 is not better than -2: no change.
29	L7	round=3 edge=3 → 1 candidate=2	Round 3, 3 → 1: 4 + -2 = 2 is not better than 2: no change.
30	L7	round=3 edge=4 → 3 candidate=5	Round 3, 4 → 3: -2 + 7 = 5 is not better than 4: no change.
31	L9	round=3	Round 3 changed nothing, so no later round can: stop early.
32	L12	return=[0, 2, 7, 4, -2] relaxations=7	No edge improves in the check pass: no negative cycle is reachable. Distances: [0, 2, 7, 4, -2]. Cost O(n · m).

35.05.2

Heuristics

Common tweaks change the queue discipline. **SLF** (small label first) puts a vertex at the front instead of the back when its new distance is smaller than the front vertex's; **LLL** (large label last) moves a vertex with an above-average distance to the back. They often cut the work on random inputs.

None of them changes the worst case. They are rules of thumb that help on some inputs and can hurt on others, so measure on realistic data before relying on one. The code below is SLF; it computes the same distances as the plain queue.

Java

1static long[] spfaSlf(int n, List<int[]>[] adj, int s) {          // small label first; null on a reachable negative cycle
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n];
4    Arrays.fill(dist, INF);
5    dist[s] = 0;
6    int[] len = new int[n];
7    boolean[] inQ = new boolean[n];
8    Deque<Integer> q = new ArrayDeque<>();
9    q.add(s);
10    inQ[s] = true;
11    while (!q.isEmpty()) {
12        int u = q.pollFirst();
13        inQ[u] = false;
14        for (int[] e : adj[u]) {
15            if (dist[u] + e[1] >= dist[e[0]]) continue;
16            dist[e[0]] = dist[u] + e[1];
17            len[e[0]] = len[u] + 1;
18            if (len[e[0]] >= n) return null;
19            if (inQ[e[0]]) continue;
20            inQ[e[0]] = true;
21            if (!q.isEmpty() && dist[e[0]] < dist[q.peekFirst()]) q.addFirst(e[0]); else q.addLast(e[0]);   // better than the front: go first
22        }
23    }
24    return dist;
25}

35.05.3

Pathological worst case

A vertex is re-queued every time its distance improves after it was already processed. If the direct edges from the source make later vertices look cheaper, and a chain of cheap edges runs backwards, each new improvement ripples through all the earlier vertices again. The trap(k) graph below does this: k + 1 vertices and about 2k edges.

The number of times vertices are queued then grows with the square of k: the test code measured 211, 821, 3,241 and 12,881 insertions for k = 20, 40, 80 and 160, so doubling k roughly quadruples the work, far above the number of edges. Dijkstra's heap handles the same graph in O(k log k). Such inputs are routinely made on purpose for programming contests.

Java

1static List<int[]>[] trap(int k) {                                // vertices 0..k; adj[u] = {v, w}
2    List<int[]>[] adj = new List[k + 1];
3    for (int i = 0; i <= k; i++) adj[i] = new ArrayList<>();
4    for (int i = 1; i <= k; i++) adj[0].add(new int[]{i, 10 * k - 2 * i});   // direct edges: later vertices look cheaper
5    for (int i = 2; i <= k; i++) adj[i].add(new int[]{i - 1, 1});            // a chain walking backwards
6    return adj;
7}
8static long enqueues(int n, List<int[]>[] adj, int s) {           // how many times the plain-queue SPFA adds a vertex
9    long INF = Long.MAX_VALUE / 2, count = 1;
10    long[] dist = new long[n];
11    Arrays.fill(dist, INF);
12    dist[s] = 0;
13    boolean[] inQ = new boolean[n];
14    Deque<Integer> q = new ArrayDeque<>();
15    q.add(s);
16    inQ[s] = true;
17    while (!q.isEmpty()) {
18        int u = q.poll();
19        inQ[u] = false;
20        for (int[] e : adj[u])
21            if (dist[u] + e[1] < dist[e[0]]) {
22                dist[e[0]] = dist[u] + e[1];
23                if (!inQ[e[0]]) { q.add(e[0]); inQ[e[0]] = true; count++; }
24            }
25    }
26    return count;
27}

35.05.4

Why SPFA is not guaranteed fast

SPFA's worst case is the same O(n · m) as Bellman-Ford, and unlike Bellman-Ford it has no clean bound on the number of passes. There is no known queue rule that makes it faster in the worst case, and the average case depends on the input family: random sparse graphs are easy, grids and crafted graphs are not.

When the weights are non-negative, use Dijkstra instead: it has a guaranteed bound. When weights can be negative and the bound matters, use Bellman-Ford, or Johnson's reweighting when many sources are needed. Use SPFA when you have measured it on data like yours.

Algorithm	Handles negative edges	Worst case	Comment
Dijkstra (binary heap)	no	O((n + m) log n)	the default for non-negative weights
Bellman-Ford	yes	O(n · m)	simple, detects negative cycles, guaranteed
SPFA	yes	O(n · m)	often fast, easy to make slow, no better bound
DAG relaxation	yes	O(n + m)	needs an acyclic graph

Practice ladder

Now try it yourself

Easy

Network Delay Time

Medium

Cheapest Flights Within K Stops
Path with Maximum Probability

Advanced

Minimum Cost to Reach Destination in Time

Key takeaways

SPFA is Bellman-Ford with a queue of vertices whose distance just improved.
Track the number of edges on each best path; n edges means a negative cycle.
Queue-order heuristics such as SLF help on some inputs and do not change the worst case.
Crafted graphs make SPFA do far more than O(n + m) work; prefer Dijkstra or Bellman-Ford when a guarantee matters.