When BFS Isn't Enough: From SPFA to Dijkstra on Network Delay Time

TL;DR: I accidentally implemented SPFA while thinking I was doing “BFS with relaxation,” then had to build a min-heap from scratch before I could do Dijkstra properly. The benchmarking that followed revealed a clean crossover point that shifts with graph density and size.

Source code: seanwilliamcarroll/ds — raw benchmark data: release

The Problem

LeetCode 743 — Network Delay Time: you have a directed, weighted graph of n nodes. Send a signal from node k. Return the minimum time until all nodes have received it, or -1 if any node is unreachable.

Signal from node 2 reaches 1 and 3 at t=1, then 4 at t=2. Answer: 2 — the time at which the last node is reached.

This is a shortest-path problem in disguise. The answer is the maximum over all nodes of the shortest path from k. You’re not looking for a shortest path — you’re computing the shortest path to every node simultaneously.

My First Attempt: Accidentally Inventing SPFA

My instinct was BFS. The wrinkle with weighted graphs is that the first time you visit a node isn’t necessarily via the shortest path. My fix: if we later discover a shorter path to a node, re-enqueue it so its neighbors can be updated.

std::deque<SearchState> neighbor_queue{{.next_node = k, .cost_to_reach = 0}};

while (!neighbor_queue.empty()) {
    const auto state = neighbor_queue.front();
    neighbor_queue.pop_front();
    if (minimum_time_from_k[state.next_node] > state.cost_to_reach) {
        minimum_time_from_k[state.next_node] = state.cost_to_reach;
        for (const auto &[neighbor, weight] : node_to_neighbors[state.next_node]) {
            neighbor_queue.push_back({neighbor, state.cost_to_reach + weight});
        }
    }
}

It works. It handles re-relaxation, terminates, and passes all the tests. I was fairly happy with it.

Claude pointed out this algorithm has a name: SPFA (Shortest Path Faster Algorithm). It’s a known variant of Bellman-Ford using a queue instead of repeated full-graph sweeps. Correct for non-negative weights, but worst-case O(V·E) — nodes can be visited many times depending on input shape.

The problem is that re-enqueue. On a dense graph, discovering a shorter path to node X means re-enqueuing all of X’s neighbors — each of which might trigger further re-enqueues of their neighbors. The cascade isn’t bounded by anything except the structure of the graph. A node that sits at a hub with many incoming edges of varying weights can be re-enqueued once per improvement, and each re-enqueue fans out to all its neighbors.

The right tool for non-negative weighted shortest paths is Dijkstra’s algorithm, which guarantees each node is settled exactly once. To implement Dijkstra, I needed a min-heap.

A Necessary Detour: Building a Min-Heap

I’d used std::priority_queue before but never understood the internals. Before implementing Dijkstra, I wanted to build one from scratch — a flat-array binary heap with bubble_up and bubble_down.

Claude wrote a 20-test suite covering edge cases (empty heap, duplicates, negative values, interleaved push/pop, and a std::pair<int,int> test simulating Dijkstra’s (distance, node) usage). I implemented MinHeap<T> against those tests.

Dijkstra Properly

With a working min-heap, Dijkstra’s core loop is similar to SPFA’s — but the heap means we always expand the globally cheapest node next, and one additional check means we never process a node twice:

MinHeap<std::pair<int, int>> search_frontier;
search_frontier.push({0, k});

while (!search_frontier.empty()) {
    auto [time_so_far, node] = search_frontier.pop();
    if (time_so_far > minimum_time_from_k[node]) { continue; } // stale entry
    for (const auto &[next_node, weight] : node_to_neighbors[node]) {
        auto new_time = time_so_far + weight;
        if (minimum_time_from_k[next_node] > new_time) {
            minimum_time_from_k[next_node] = new_time;
            search_frontier.push({new_time, next_node});
        }
    }
}

The stale entry check is the key line. When a shorter path to a node is found after it’s already in the heap, the old entry stays — there’s no “decrease-key.” When we pop it later with a worse cost, we skip it. Without this, Dijkstra degrades toward SPFA — processing the same node multiple times. With it, each node is settled exactly once, giving O((V+E) log V).

Implementing Dijkstra also cleaned up the SPFA code. My original SPFA tracked prev_node in every queue entry solely to look up edge weights from a separate unordered_map<Edge, int> — which required a custom Edge struct with a hash specialization. Moving to (dest, weight) pairs directly in the adjacency list — the same representation Dijkstra uses — eliminated the map, the struct, and the hash.

Benchmarking

Two implementations of the same problem, different data structures underneath (deque vs min-heap). The natural question: does it matter, and when?

Claude wrote a Google Benchmark harness and visualization script at my direction. The interesting design problem was graph generation: random edges risk disconnected graphs, so every generated graph starts with a chain 1→2→...→n guaranteeing reachability, then adds random edges on top. Density is parameterized as a percentage of the extra edges above the chain — 0% is a pure chain, 100% is all possible directed edges.

The benchmark ran a cartesian product: n ∈ {10, 25, 50, 100, 200, 500} × density ∈ {0, 5, 10, 15, 20, 25, 50, 75, 100%}.

What the Numbers Said

The crossover density shifts left as n grows. SPFA is only faster at low density (few paths to re-relax), but the threshold drops as the graph gets larger:

The chain advantage is flat. At density=0%, SPFA consistently beats Dijkstra by ~5% regardless of n. A chain has one path to each node, so SPFA never re-enqueues — the only difference is O(1) deque operations vs O(log n) heap operations for the same linear traversal. The gap doesn’t grow because chain length adds linearly to both algorithms’ work.

The Dijkstra advantage compounds. At 100% density:

This is the re-enqueue cascade in action. On a fully connected graph, every time SPFA improves a node’s distance, it re-enqueues all of that node’s neighbors — and with high connectivity, that’s most of the graph. The number of redundant node visits grows super-linearly with both size and density. Dijkstra avoids this entirely: once a node is popped from the heap, it’s settled.

The heatmap made the crossover band immediately obvious: a diagonal boundary running from upper-left (small n, low density — SPFA territory) to lower-right (large n, any density — Dijkstra territory).

What I Took Away

I came into this problem expecting to implement Dijkstra. What actually happened: I implemented SPFA without knowing it, got corrected by name, had to stop and build a min-heap from scratch, then came back and did the thing I’d set out to do.

The benchmarking wasn’t planned — it came from a natural question once both implementations existed. The answer was cleaner than I expected: Dijkstra is the right default for non-negative weighted shortest paths, but SPFA isn’t just “wrong Dijkstra.” On a chain or near-chain graph, it genuinely wins. The crossover happens earlier than you might think — at n=200, even 5% density is enough for the heap to pay for itself.