SPFA

SPFA (Shortest Path Faster Algorithm) finds the shortest distances from one vertex in a directed graph with negative edge weights, like Bellman–Ford, but it re-checks only the edges out of vertices whose distance has just dropped. It also detects negative cycles. Its worst case is still $O (nm)$ , so if no weight is negative, use Dijkstra's algorithm instead.

Explanation

A game level has 4 rooms joined by one-way passages, and walking through a passage costs coins. From room 1, the passage to room 2 costs 2 coins and the passage to room 3 costs 3. The passage from room 2 to room 4 costs 2. The passage from room 3 to room 2 has a chest that pays 2 coins more than the walk costs, so its cost is −2. Bellman–Ford finds the cheapest way from room 1 to every room by checking all 4 passages in every round. Say it checks the passages out of room 1 first, then the one from room 2 to room 4, then the chest. Round 1 gives room 4 the number 2 + 2 = 4 before the chest lowers room 2 to 1, round 2 lowers room 4 to 3, and round 3 changes nothing. That is 12 checks, and 7 of them change nothing.

A passage can give its end a lower number only if the number at its start dropped since the passage was last checked. So let's keep a queue of rooms to look at again: the rooms whose number dropped. Room 1 starts in the queue alone, with 0. Take the first room from the queue, check only the passages out of it, and put every room whose number drops at the back, as in BFS.

SPFA on the 4-room level from room 1, step 1.

Room 1 gets 0 and waits in the queue alone.

1/10

Fig. 1. Step through SPFA on the 4 rooms. The ringed room is taken from the queue, a blue arrow lowers a number, and the boxes below are the queue.

Room 2 was already waiting in the queue when the chest lowered it to 3 − 2 = 1, so it isn't added twice: it is taken once, with 1. Every room was taken once, as in BFS. The queue empties after 4 checks instead of 12, with the same answers as Bellman–Ford: 0, 1, 3 and 3.

On a bigger level, a chest can lead back to a room that has already left the queue. This level has 6 rooms and 8 passages, and the chest is on the passage from room 5 back to room 2. We look for the cheapest route from room 1 to room 6.

A level of 6 rooms with one-way passages and their costs; from start room 1 a red route through rooms 2, 4 and 6 costs 6, and a blue route through rooms 3 and 5, back along the −3 passage to room 2, then through rooms 4 and 6 costs 4.

Fig. 2. Two routes from room 1 to room 6. The blue one uses the chest to go back to room 2.

The red route through rooms 2 and 4 costs 2 + 2 + 2 = 6. The blue route goes through rooms 3 and 5, takes the chest back to room 2 and then goes on through room 4: 1 + 2 − 3 + 2 + 2 = 4.

In BFS, a room taken from the queue is finished and never goes back in. Let's keep that rule here. Room 1 gives room 2 the number 2 and room 3 the number 1. Room 2 is taken and gives room 4 the number 4, room 3 gives room 5 the number 3, and room 4 gives room 6 the number 6. Then room 5 is taken, and the chest lowers room 2 to 3 − 3 = 0. But room 2 is finished, so its passage to room 4 is never checked again. The queue empties with 6 next to room 6: the red route.

Room 2's passages were checked with the number 2, so those checks are out of date. A room whose number drops must go back into the queue, even if it was taken before. Here room 2 goes back in behind room 6, with 0, and its passages get checked again with the new number. The run stops when the queue is empty: then no room's number has dropped since its passages were checked, so no passage can lower anything.

This is SPFA: Bellman–Ford that re-checks only the passages out of rooms whose number dropped, kept in a queue. A room can enter the queue several times, but it never waits there twice at once.

SPFA on the 6-room level from room 1, step 1.

Room 1 gets 0 and enters the queue for the 1st time.

1/22

Fig. 3. Step through SPFA on the 6-room level. The ringed room is taken from the queue, a blue arrow lowers a number, a grey arrow changes nothing, and the boxes below are the queue. The count after a room's number says how many times it has entered the queue.

The run found 0, 0, 1, 2, 3 and 4 coins for rooms 1 to 6, the same as Bellman–Ford, in 9 takes.

Negative cycles

Let the chest on the passage from room 5 to room 2 pay 5 coins more than the walk, so its cost is −5. The loop from room 2 through rooms 4 and 5 and back to room 2 costs 2 + 2 − 5 = −1, a negative cycle. Here the queue never empties. Every trip around the loop lowers room 2 again and puts it back, and room 4, room 5 and room 6 follow. Room 6 gets 6, then 2, 1, 0, −1, and so on.

Bellman–Ford stops after $n - 1$ n - 1 rounds and runs a check round. SPFA has no rounds to count, so it counts how many times each room enters the queue. Without a negative cycle, a room enters at most $n - 1$ n - 1 times (the correctness proof shows why). A room that enters for the $n$ -th time, the 6th time on this level, proves a negative cycle. Here this happens to room 2 at the 21st take: room 5 is taken with −1 and lowers room 2 from −5 to −6.

The six-room level with the chest costing −5: the loop from room 2 to room 4 to room 5 and back to room 2 is red and costs −1, rooms 2, 4, 5 and 6 are shaded, and the entry counts are 1, 6, 1, 5, 5 and 5 for rooms 1 to 6, with room 2 just changed from 5 to 6.

Fig. 4. Room 2 enters the queue for the 6th time. The red loop costs −1 per trip.

Rooms 2, 4, 5 and 6 have no cheapest route at all, because they can be reached from the loop. To find all such rooms, run Bellman–Ford: the rooms whose number still drops in its check round lie on a negative cycle or behind one, and a DFS from them marks every room they reach.

Implementation

In the code, rooms are vertices, passages are directed edges from u to v, and a passage's cost is the edge's weight w. The number next to room v is d[v], the shortest distance from the start, vertex 1, to v found so far. Checking a passage is relaxing the edge from u to v, as in Bellman–Ford. Taking a vertex means relaxing the edges out of it, so the graph is stored as an adjacency list: adj[u] holds the pairs (v, w).

The queue holds the vertices whose d[v] dropped since their edges were last relaxed. A vertex in the queue is waiting, and the array inQueue marks it, so that a waiting vertex is not pushed a second time. Each push of v into the queue is one entry, and cnt[v] counts the entries of v.

Initialise: d[1] = 0, every other d[v] = INF; the queue holds vertex 1, which is waiting and has 1 entry.
Take the next vertex: u from the front of the queue; it is no longer waiting.
Relax its edges: for each edge from u to v of weight w, if d[u] + w < d[v], set d[v] = d[u] + w.
Add it to the queue: if d[v] just dropped and v is not waiting, push v, mark it waiting and count the entry.
Check for a negative cycle: after a push, if cnt[v] == n, stop with "negative cycle".
Stop when the queue is empty.

The program reads n and m, then m lines u v w: a one-way edge from u to v of weight w. The start is vertex 1. It prints negative cycle, or the shortest distance to each vertex, with * for a vertex that can't be reached. For the main graph the input is:

The edges out of each vertex are kept in input order, which is the order of the explanation. d, cnt and inQueue are indexed by vertex from 1 to n.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const long long INF = 99;   // small for the demo; use 1e18 for real inputs

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, long long>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    // initialise
    vector<long long> d(n + 1, INF);
    vector<int> cnt(n + 1, 0);
    vector<bool> inQueue(n + 1, false);
    queue<int> q;
    d[1] = 0;
    q.push(1);
    inQueue[1] = true;
    cnt[1] = 1;

    while (!q.empty()) {
        // take the next vertex
        int u = q.front();
        q.pop();
        inQueue[u] = false;

        // relax its edges
        for (auto [v, w] : adj[u]) {
            if (d[u] + w < d[v]) {
                d[v] = d[u] + w;
                // add it to the queue
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    cnt[v]++;
                    // check for a negative cycle
                    if (cnt[v] == n) {
                        cout << "negative cycle\n";
                        return 0;
                    }
                }
            }
        }
    }

    // stop: the queue is empty
    for (int v = 1; v <= n; v++) {
        if (d[v] == INF) cout << '*';
        else cout << d[v];
        cout << (v < n ? ' ' : '\n');
    }
}

Only vertices that have been reached enter the queue, so d[u] is never INF when u is taken, and the check d[u] != INF from Bellman–Ford isn't needed. For an undirected graph, store each edge in both directions; a negative undirected edge is then a negative cycle by itself.

Without a negative cycle each vertex enters the queue at most $n - 1$ n - 1 times, and each take relaxes the edges out of one vertex, so all takes together make at most $(n - 1) \cdot m$ (n - 1) \cdot m relaxations. The time is $O (nm)$ , the same bound as Bellman–Ford, and the memory is $O (n + m)$ O(n + m).

Tests can reach this bound. On this graph of 5 vertices, every vertex has an edge to every higher vertex, of weight $(j - i)^{2}$ (j - i)^2 for the edge $i \to j$ i \to j, and the edges out of each vertex are listed from the farthest:

The shortest path to vertex $k$ goes through every vertex before it and has length $k - 1$ k - 1. SPFA finds cheaper and cheaper paths to vertex 5 one after another: it gets 16, 10, 8, 6 and finally 4. It enters the queue 4 times, which is $n - 1$ n - 1; the drop from 10 to 8 happens while it is waiting.

Sparse graphs are no safer. Give vertex 1 an edge to each vertex $i$ of weight $2 i$ , listed from $i = n$ i = n down to $i = 2$ i = 2, and add a path from vertex 2 through 3, 4 and so on to vertex $n$ , with weight 1 on each edge. Vertex $n$ enters the queue $n - 1$ n - 1 times, and SPFA makes $n (n - 1) /2$ n(n - 1)/2 relaxations. With $n = 1 0^{5}$ n = 10^5 and $m = 199997$ m = 199\,997 that is about $5 \cdot 1 0^{9}$ 5 \cdot 10^9 relaxations. Dijkstra relaxes each edge once.

Which lines complete step 4?

if (d[u] + w < d[v]) {
    d[v] = d[u] + w;
    // your lines here
}

if (!inQueue[v]) { q.push(v); inQueue[v] = true; cnt[v]++; }

q.push(v); cnt[v]++;

if (cnt[v] == 0) { q.push(v); cnt[v]++; }

A negative cycle anywhere

Some problems ask whether there is a negative cycle anywhere in the graph, not only one reachable from vertex 1. With 3 vertices and the edges $2 \to 3$ 2 \to 3 of weight 1 and $3 \to 2$ 3 \to 2 of weight −2, the cycle between vertices 2 and 3 has length −1, but nothing is reached from vertex 1: the queue empties after the first take, and the program reports no cycle. As in Bellman–Ford, start with every d[v] = 0 and every vertex in the queue, as if a new vertex had an edge of weight 0 to each of them. With the new vertex the graph has $n + 1$ n + 1 vertices, so a vertex may enter $n$ times without a negative cycle. The first of those entries is the initial push, so we set cnt[v] = 0 for it: at most $n - 1$ n - 1 entries are counted, and cnt[v] == n still means a negative cycle. Replace the initialisation of the queue with:

for (int v = 1; v <= n; v++) {
    d[v] = 0;
    q.push(v);
    inQueue[v] = true;
    cnt[v] = 0;
}

On the 3-vertex graph, vertex 2 comes back into the queue for the 3rd time at the 7th take, and the program prints negative cycle. To print the cycle itself, as problem 5178 asks, use Bellman–Ford's check round and its walk back along parent.

Correctness proof

Every finite $d_{v}$ d_v is the length of a real path from $s$ to $v$ , because it was set by a relaxation along an edge. So $d_{v}$ d_v is never below the shortest distance.

The algorithm keeps this invariant: every vertex whose $d_{v}$ d_v has dropped since its edges were last relaxed is waiting in the queue. At the start only $s$ has a value, and it waits. A relaxation that lowers $d_{v}$ d_v pushes $v$ , unless it is waiting already. Taking $u$ relaxes all its edges with the current $d_{u}$ d_u. So when the queue is empty, no edge can lower anything: $d_{u} + w \geq d_{v}$ d_u + w \ge d_v for every edge $u \to v$ u \to v. Then each $d_{v}$ d_v equals the shortest distance, as in Bellman–Ford: follow a shortest path edge by edge, and each $d$ along it is at most the length of the path so far.

To bound the entries of a vertex by $n - 1$ n - 1, split the run into passes. Pass 1 is $s$ alone, and pass $k + 1$ k + 1 is the vertices pushed while pass $k$ was being taken. On the main graph the queue order is 1 | 2, 3 | 4, 5 | 6, 2 | 4 | 6: six passes (Fig. 5).

The 6-vertex graph with the path 1→3→5→2→4→6 drawn in blue, and below it the queue order in six boxes, one per pass: 1, then 2 3, then 4 5, then 6 2, then 4, then 6.

Fig. 5. The shortest path to vertex 6, and the queue order with one box per pass. Each pass does at least what a Bellman–Ford round does, and a vertex appears in a pass at most once.

After pass $k$ , $d_{v}$ d_v is at most the length of the shortest path to $v$ with at most $k$ edges. This is Bellman–Ford's invariant, with passes for rounds. Take such a path and its last edge $u \to v$ u \to v. After pass $k - 1$ k - 1, $d_{u}$ d_u is at most the length of the path up to $u$ . After the last drop of $d_{u}$ d_u, $u$ is in the queue: pushed then, or already waiting. So it is taken with this value in pass $k$ at the latest, and the edge $u \to v$ u \to v is relaxed then. In Fig. 5, after pass $k$ the first $k$ vertices of the blue path after vertex 1 have their final $d$ .

Without a negative cycle, a shortest path has at most $n - 1$ n - 1 edges, so every $d_{v}$ d_v is final after pass $n - 1$ n - 1, and pass $n$ pushes nothing. On the main graph, pass 6 pushes nothing. A vertex is in a pass at most once, because a waiting vertex isn't pushed again, and a vertex other than $s$ is never in pass 1. So it is in at most passes 2 to $n$ : at most $n - 1$ n - 1 entries. The start $s$ never comes back, since $d_{s}$ d_s could drop below 0 only through a negative cycle.

With a negative cycle reachable from $s$ , the queue never empties: if it did, no edge of the cycle could lower its end, and adding these inequalities around the cycle gives the cycle a length of at least 0, as in Bellman–Ford. So the run never ends, and since there are finitely many vertices, some vertex enters for the $n$ -th time.

Common mistakes

Treating a taken vertex as finished, as in BFS, with a visited array instead of inQueue, so a vertex whose distance drops after it was taken never goes back. Clear the flag when a vertex is taken, so it can come back.
Pushing a vertex that is already waiting, or counting every drop of d[v] instead of entries. This adds work and can report a negative cycle in a graph whose weights are all positive; use the inQueue flag and count entries.
Reporting a negative cycle at $n - 1$ n - 1 entries, which a vertex can reach without one. Stop at cnt[v] == n.
Using SPFA on a graph with no negative weights because it is usually faster. Tests can force its $O (nm)$ worst case, as the sparse graph above does, so use Dijkstra.

Similar algorithms

Bellman–Ford relaxes every edge in every round. Its rounds make it the right tool for paths with at most $k$ edges, which SPFA can't count, and it is simpler for printing a negative cycle.

Dijkstra's algorithm takes the closest vertex instead of the oldest, so each vertex is taken once, and runs in $O ((n + m) lo g m)$ O((n + m) \log m) in the worst case. It needs every weight to be non-negative.

BFS is the special case where every edge has the same length: the first time a vertex is reached is final.

Practice

Ford-Bellman#1453

Very easy · Shortest paths

Wormholes#1108

Medium · Graphs · Shortest paths

Cycle#5178

Easy · Graphs · Shortest paths

Arbitrage#6664

Medium · Shortest paths · Graphs

Shortest Paths#2968

Very easy · Graphs

Flights#4456

Easy · Dynamic programming · Graphs

Distance between the vertices#2965

Very easy · Dijkstra algorithm · Shortest paths · Priority Queue

Was this page helpful?