SPFA (Shortest Path Faster Algorithm)

SPFA is a queue-based refinement of Bellman-Ford. Instead of relaxing every edge $V - 1$ times, it keeps a FIFO queue of vertices whose tentative distance has recently decreased, and only relaxes the edges out of those vertices. A vertex that is not currently in the queue is pushed whenever its tentative distance drops. The algorithm terminates when the queue empties.

In the worst case SPFA is still $O(V E)$ — adversarial graphs can force every edge to be relaxed $V - 1$ times — but on typical sparse graphs with few negative edges it is often many times faster than plain Bellman-Ford. Like Bellman-Ford, it handles negative edge weights and can report a negative cycle reachable from the source: if any vertex is relaxed more than $V - 1$ times, there is one.

The solve function takes [n, edges, source] with edges as [u, v, w] triples and returns the distance array using 10**18 for unreachable vertices, or [] if a negative cycle is reachable.

Codes

Python

from collections import deque

def solve(xs):
    """xs = [n, edges, source]. Return distances, or [] on negative cycle."""
    n, edges, source = xs
    INF = 10**18
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    dist = [INF] * n
    dist[source] = 0
    in_queue = [False] * n
    count = [0] * n
    q = deque([source])
    in_queue[source] = True
    while q:
        u = q.popleft()
        in_queue[u] = False
        for v, w in adj[u]:
            nd = dist[u] + w
            if nd < dist[v]:
                dist[v] = nd
                count[v] += 1
                if count[v] >= n:
                    return []          # negative cycle reachable
                if not in_queue[v]:
                    q.append(v)
                    in_queue[v] = True
    return dist

C++

#include <array>
#include <deque>
#include <vector>

const long long INF = (long long)1e18;

std::vector<long long> spfa(int n,
        const std::vector<std::array<int, 3>>& edges, int source) {
    std::vector<std::vector<std::pair<int, int>>> adj(n);
    for (auto& e : edges) adj[e[0]].push_back({e[1], e[2]});
    std::vector<long long> dist(n, INF);
    std::vector<int> count(n, 0);
    std::vector<char> in_queue(n, 0);
    dist[source] = 0;
    std::deque<int> q;
    q.push_back(source); in_queue[source] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop_front();
        in_queue[u] = 0;
        for (auto [v, w] : adj[u]) {
            long long nd = dist[u] + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                if (++count[v] >= n) return {}; // negative cycle
                if (!in_queue[v]) { q.push_back(v); in_queue[v] = 1; }
            }
        }
    }
    return dist;
}

Example

Loading Python runner...

Description

Run time analysis

$O(V E)$ worst case, same as Bellman-Ford. On random or typical sparse graphs it is usually closer to $O(k E)$ for a small constant $k$ — each vertex is only re-enqueued when its distance strictly improves — but hand-crafted adversarial inputs (grid-like graphs with specific weights) can realise the worst case.

Space analysis

$O(V + E)$. The adjacency list is $O(V + E)$; the distance, in-queue, and relaxation-count arrays together with the FIFO queue add $O(V)$.

Proof of correctness

Partial correctness (no negative cycle). Let $\delta(s, v)$ denote the true shortest-path distance. We claim that when the queue empties, $dist[v] = \delta(s, v)$ for every vertex $v$ reachable from $s$.

The following invariant holds throughout the run: for every vertex $v$, if $dist[v]$ is currently greater than $\delta(s, v)$, then either $v$ is already in the queue, or there exists a vertex $u$ in the queue with $dist[u] + \text{(some path weight from } u \text{ to } v\text{)} = \delta(s, v)$. Concretely, any vertex that still has a suboptimal tentative distance is guaranteed to be reached again, because whenever we pop a vertex $u$ and find a shorter route through $u$ to a neighbour $v$, we push $v$ onto the queue.

More formally, SPFA performs the same relaxations as a Bellman-Ford sweep, just in a different order. By the Bellman-Ford correctness argument (induction on path length; see the Bellman-Ford page), after relaxing every edge at most $V - 1$ times on every shortest path $s \to v$ we reach $dist[v] = \delta(s, v)$. SPFA relaxes $(u, v)$ whenever $dist[u]$ decreases, so the subsequence of relaxations it performs along any fixed shortest path $s \to v_1 \to v_2 \to \dots \to v_k$ is in order, and each prefix distance stabilises before the next relaxation is triggered. After at most $V - 1$ relaxations per edge in the worst case, every reachable vertex has its final value and no more changes occur, so the queue drains.

Negative-cycle detection. Every relaxation of a vertex $v$ strictly decreases $dist[v]$. If no negative cycle is reachable from $s$, then $dist[v]$ cannot drop below $\delta(s, v)$, and because every relaxation along any shortest path corresponds to a distinct edge on that path (a simple shortest path has at most $V - 1$ edges), $v$ can be relaxed at most $V - 1$ times. So if the counter reaches $V$, there is no simple walk from $s$ to $v$ that could explain that many strict decreases — the only remaining possibility is that some cycle on an $s \to v$ walk has negative total weight. Reporting a negative cycle in that case is correct.

Extensions

Applications

References

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 3rd ed., Chapter 24 (Single-Source Shortest Paths).
• Bellman, R. (1958). "On a routing problem." Quarterly of Applied Mathematics, 16(1), 87-90.
• cp-algorithms — Bellman-Ford and SPFA