Bellman-Ford Algorithm

Quick Revisit

• USE WHEN: Shortest paths with negative edge weights, or need to detect negative cycles
• INVARIANT: After round $k$, all shortest paths using ≤ $k$ edges are correct
• TIME: O(VE) | SPACE: O(V)
• CLASSIC BUG: Not running a V-th relaxation pass to detect negative cycles (or not propagating -∞ to affected nodes)
• PRACTICE: 05-ladder-graphs

AL-16 | Single-source shortest paths that handles negative edge weights -- the algorithm Dijkstra can't replace. Also detects negative-weight cycles reachable from the source.

Difficulty: [Intermediate]Prerequisites: Graph RepresentationCF Rating Range: 1600 -- 1900

---

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Further Reading

---

Intuition

The Pain

Consider this 5-node graph with a negative edge. Source = 0:

         1              3
    0 --------> 1 --------> 4
    |           ^
    |           | -6
    | 4         |
    v           |
    2 --------> 3
         2

Edges: $(0,1,1)$, $(0,2,4)$, $(2,3,2)$, $(3,1,-6)$, $(1,4,3)$.

Dijkstra greedily finalizes the closest unvisited node and never looks back. Watch it fail:

  Step | Pick | Finalize | Relax             | dist[]
  -----+------+----------+-------------------+-------------------------
    0  |  --  |    --    | --                | [0, INF, INF, INF, INF]
    1  |  0   |  d[0]=0  | (0,1,1), (0,2,4) | [0,  1,  4, INF, INF]
    2  |  1   |  d[1]=1  | (1,4,3)           | [0,  1,  4, INF,  4 ]
    3  |  2   |  d[2]=4  | (2,3,2)           | [0,  1,  4,  6,   4 ]
    4  |  4   |  d[4]=4  | (none)            | [0,  1,  4,  6,   4 ]
    5  |  3   |  d[3]=6  | (3,1,-6): 6-6=0   | d[1] already locked!

Dijkstra finalizes $d[1]=1$ in step 2 and never revisits it. The true shortest path to node 1 is $0\to 2\to 3\to 1$ with cost $4+2-6=0$. Dijkstra returns $d[1]=1$ and $d[4]=4$. Both wrong.

We need an algorithm that can revise distances as cheaper paths are discovered through negative edges. Enter Bellman-Ford.

The Key Insight

Relax every edge $n-1$ times -- after $k$ rounds, all shortest paths using at most $k$ edges are correct.

Think of it like rumor spreading in a town. On day 1 the source tells its direct neighbors the news -- they now know their 1-hop distance. On day 2 those neighbors pass it along -- every node reachable in 2 hops has the correct distance. Each round, the "frontier" of correct knowledge extends by one hop. A shortest path in an $n$-node graph uses at most $n-1$ edges, so after $n-1$ days the whole town knows.

Core loop (3 lines of logic):

for i = 1 to n-1:
    for every edge (u, v, w):
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w

Visual Walkthrough

Same graph, source = 0. Edge processing order: $(1,4,3)$, $(3,1,-6)$, $(2,3,2)$, $(0,2,4)$, $(0,1,1)$.

  Round |  d[0]  d[1]  d[2]  d[3]  d[4]  | What changed
  ------+----------------------------------+----------------------------
  init  |   0    INF   INF   INF   INF    |
        |                                  |
    1   |   0     1     4    INF   INF    | (0,2,4): d[2]=4
        |                                  | (0,1,1): d[1]=1
        |                                  |
    2   |   0     1     4     6     4     | (2,3,2): 4+2=6 -> d[3]
        |                                  | (1,4,3): 1+3=4 -> d[4]
        |                                  |
    3   |   0     0     4     6     4     | (3,1,-6): 6-6=0 -> d[1]
        |                                  |
    4   |   0     0     4     6     3     | (1,4,3): 0+3=3 -> d[4]
        |                                  |
  (n-1 = 4 rounds complete, all shortest paths found)

After round 1: nodes reachable in 1 edge are correct ($d[1]$, $d[2]$). After round 2: nodes reachable in 2 edges are correct ($d[3]$, $d[4]$). After round 3: the 3-hop path $0\to 2\to 3\to 1$ corrects $d[1]$ to 0. After round 4: the 4-hop path $0\to 2\to 3\to 1\to 4$ corrects $d[4]$ to 3.

Two Mental Models: Negative Edge vs Negative Cycle

It is worth separating two ideas that get conflated in beginner explanations.

Model A — negative edges, no negative cycles. Some edges have negative weight, but every reachable cycle still has non-negative total weight. Shortest paths are well-defined; they just cannot be found by a greedy algorithm that finalises on first contact (Dijkstra). After $n-1$ rounds Bellman-Ford has the right answer for every node, exactly as if the weights were positive.

Model B — a reachable negative cycle. Some cycle reachable from the source has total weight < 0. Now "shortest path" is not even well-defined for any node reachable through that cycle: by going around it again you can decrease the cost without bound. Bellman-Ford detects this on round $n$ — any further relaxation is proof that a finite $n-1$-edge bound was wrong, which is only possible if the optimal path is decreasing forever.

The slogan: a negative edge is legal; a reachable negative cycle is fatal. Most contest problems live in Model A. The few that live in Model B usually want one of:

• "Is there a negative cycle reachable from $s$?" (yes/no).
• "Print one." (trace parents from a node relaxed on round $n$).
• "Which nodes have undefined shortest path?" (any node reachable from a node relaxed on round $n$, propagated by BFS/DFS).

2.4 The Invariant

+------------------------------------------------------------------+
|  After round k, dist[v] <= the length of any path from source    |
|  to v using at most k edges.                                     |
|                                                                  |
|  After n-1 rounds, dist[v] is the true shortest-path distance    |
|  (since a shortest simple path has at most n-1 edges).           |
+------------------------------------------------------------------+

Why $n-1$ edges? A simple path visits each node at most once. With $n$ nodes, that means at most $n-1$ edges. If a "shortest path" needs $n$ or more edges, it contains a cycle -- and unless that cycle has negative weight, removing it cannot increase the cost. (If it does have negative weight, shortest paths are undefined and Bellman-Ford detects this with one extra round.)

What the Code Won't Teach You

Bellman-Ford is really DP on edge count, not "just relaxing edges until convergence."

The wrong mental model: "keep relaxing until nothing changes." This gives no insight into why n-1 rounds suffice or what each round achieves.

The correct model: define $d[k][v]$ = shortest distance from source to $v$ using at most $k$ edges. Each round computes the next row of this DP table:

  DP table: d[k][v] for the example graph (source = 0)

             v=0    v=1    v=2    v=3    v=4
  k=0 (init) [ 0    INF    INF    INF    INF ]  only source known
  k=1         [ 0     1      4    INF    INF ]  1-edge paths
  k=2         [ 0     1      4      6      4 ]  2-edge paths
  k=3         [ 0     0      4      6      4 ]  3-edge: 0->2->3->1
  k=4 (n-1)  [ 0     0      4      6      3 ]  4-edge: 0->2->3->1->4
              +----+------+------+------+-----+
  Row n-1 = final answer. No simple path in n nodes needs more
  than n-1 edges.
  In code, we flatten to 1D: d[v] is updated in-place each round.

After $n-1$ rounds, $d[n-1][v]$ holds the true shortest distance. If $d[n][v]<d[n-1][v]$ for any $v$, the path needs $n$ edges -- impossible without revisiting a node, meaning a negative cycle exists.

Detecting a negative cycle vs reasoning about it are different skills.

Detection is mechanical: run round $n$, check for improvement. But contest problems rarely stop there. Common follow-ups:

• "Can node $t$ be reached from $s$ via a negative cycle?" (reachability check)
• "What is the maximum score on a path from $s$ to $t$?" (if a negative cycle is reachable from $s$ and can reach $t$, the answer is infinity / -1 / impossible)
• "Print the cycle." (trace parent pointers backward from the relaxed node)

The detection is the easy part. The reasoning about what to do with it is where problems get hard.

Understanding Dijkstra's failure mode is prerequisite knowledge.

If you don't understand why Dijkstra fails on negative edges -- specifically, that its greedy invariant ("when we pop $u$, $d[u]$ is final") breaks when a later-processed node can provide a cheaper path via a negative edge -- then Bellman-Ford's design feels arbitrary rather than motivated. Bellman-Ford exists precisely because it doesn't assume finality at any step; it keeps revising distances for $n-1$ rounds, which is what correctness requires.

When to Reach for This

Trigger phrases in problem statements:

• "negative weights" --> Bellman-Ford or SPFA
• "detect negative cycle" --> Bellman-Ford (run the $n$-th round)
• "shortest path using at most $k$ edges" --> stop after $k$ rounds
• "system of difference constraints" --> model as graph, run Bellman-Ford
• "arbitrage" --> log-transform rates, detect negative cycle

When not to use Bellman-Ford. $O(VE)$ is slow. The contest decision is usually "Can I avoid this?" Replace it whenever you can:

• All weights non-negative --> Dijkstra is $O((V+E)\log V)$, far faster.
• Unweighted graph --> BFS is $O(V+E)$.
• All-pairs shortest paths on small $n$ --> Floyd-Warshall $O(V^3)$ is simpler.
• Dense graph, no negative edges --> Dijkstra with $O(V^2)$ scan beats $O(VE)$.
• Graph is a DAG --> DP on DAG handles negative edges in $O(V+E)$.

Reach for Bellman-Ford only when (a) the graph has negative edges and is not a DAG, or (b) you specifically need to detect or characterise a negative cycle. With $n\cdot m$ up to roughly ${10}^7$–${10}^8$ it finishes in time on CF; beyond that, look for structure that lets you avoid it.

Edge Relaxation State Diagram

How the "frontier of correct knowledge" expands round by round. Graph: edges (0,1,1), (0,2,4), (2,3,2), (3,1,-6), (1,4,3). Source = 0.

After Round 1 -- frontier covers 1-hop nodes:

         1              3
    (0)------->[1]--------> .4.     Legend:
     |           ^                  ( ) = source
     |           | -6               [v] = distance known correct
     | 4         |                   .v. = not yet reached
     v           |
    [2]--------> .3.
         2

    dist: [0, 1, 4, INF, INF]
    Correct for: all paths with <= 1 edge.
    Nodes 1 and 2 have final 1-hop distances.

After Round 3 -- frontier covers 3-hop nodes:

         1              3
    (0)------->[1*]-------> [4]     Legend:
     |           ^                  [v*] = corrected this round
     |           | -6
     | 4         |          Path 0->2->3->1 costs 4+2-6 = 0
     v           |          beats the old 1-hop d[1]=1
    [2]------->[3]
         2

    dist: [0, 0, 4, 6, 4]
    Correct for: all paths with <= 3 edges.
    Node 1 was revised downward -- this is exactly
    what Dijkstra cannot do.

Negative cycle detection -- the n-th round discovers further relaxation:

    Suppose edge (1,0,-2) existed, creating cycle 0->1->0
    with total cost 1 + (-2) = -1 (negative).

         1
    (0)-------> 1       After n-1 rounds: d = [0, 1, ...]
     ^          |
     |__________|       Round n (the extra round):
         -2               edge(1,0,-2): d[1]+(-2) = 1-2 = -1 < d[0]=0
                          --> RELAXED! Negative cycle detected.
                          --> Mark d[0] = -INF.
                          --> Propagate: all nodes reachable from 0
                              also get d[v] = -INF via BFS/DFS.

    A path with n edges in an n-node graph MUST revisit a node,
    so improvement on round n proves a cycle -- and since it
    improves the distance, the cycle weight is negative.

---

C++ STL Reference

Bellman-Ford is typically implemented from scratch (no STL graph algorithm exists), but these STL components are used in the implementation:

Function / Class	Header	What it does	Time Complexity
vector<tuple<int,int,ll>>	<vector>, <tuple>	Edge list storage (u, v, w)	$O(1)$ per access
fill(begin, end, val)	<algorithm>	Initialize dist array to INF	$O(n)$
queue<int>	<queue>	SPFA vertex queue	$O(1)$ push/pop
numeric_limits<ll>::max()	<limits>	Safe INF value (or use 1e18)	$O(1)$
auto [u, v, w] = edges[i]	(C++17 structured bindings)	Unpack edge tuple	$O(1)$
vector<vector<pair<int,ll>>>	<vector>	Adjacency list for SPFA	$O(1)$ per access

---

Implementation (Contest-Ready)

⚠️ Negative cycle detection. Run the standard n-1 iterations, then run ONE more iteration (the nth). If any distance decreases on the nth iteration, the graph contains a negative-weight cycle reachable from the source. To find which vertices are affected, any vertex relaxed in iteration n (and anything reachable from it) has dist = -infinity.

// After n-1 normal iterations:
bool has_neg_cycle = false;
for (auto& [u, v, w] : edges) {
    if (dist[u] + w < dist[v]) {
        has_neg_cycle = true;
        dist[v] = -INF;  // Mark as affected
    }
}

Version 1 -- Standard Bellman-Ford (minimal)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

struct Edge { int u, v; ll w; };

// Returns dist array. dist[v] = -INF if v is on/reachable from a negative cycle.
vector<ll> bellman_ford(int n, int src, vector<Edge>& edges) {
    vector<ll> dist(n, INF);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++)
        for (auto& [u, v, w] : edges)
            if (dist[u] < INF && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
    // Negative cycle detection: one more round
    for (auto& [u, v, w] : edges)
        if (dist[u] < INF && dist[u] + w < dist[v])
            dist[v] = -INF;
    return dist;
}

int main() {
    int n, m, src;
    cin >> n >> m >> src;
    vector<Edge> edges(m);
    for (auto& [u, v, w] : edges) cin >> u >> v >> w;
    auto dist = bellman_ford(n, src, edges);
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) cout << "INF\n";
        else if (dist[i] == -INF) cout << "-INF\n";
        else cout << dist[i] << "\n";
    }
}

Version 2 -- Standard Bellman-Ford (explained)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

struct Edge { int u, v; ll w; };

vector<ll> bellman_ford(int n, int src, vector<Edge>& edges) {
    vector<ll> dist(n, INF);
    dist[src] = 0;

    // After round i, dist[v] is optimal for paths using <= i+1 edges.
    // V-1 rounds suffice because shortest simple path has at most V-1 edges.
    for (int i = 0; i < n - 1; i++) {
        bool updated = false;
        for (auto& [u, v, w] : edges) {
            // Guard: don't relax from unreachable vertices.
            // Without this, INF + negative weight could look like a valid path.
            if (dist[u] < INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        // Early termination: if no edge relaxed this round, we're done.
        if (!updated) break;
    }

    // V-th round: if any edge still relaxes, a negative cycle is reachable.
    // Propagate -INF to all vertices reachable from the cycle.
    // Run N-1 more rounds to fully propagate (a cycle can reach far-away nodes).
    for (int i = 0; i < n - 1; i++)
        for (auto& [u, v, w] : edges)
            if (dist[u] != INF && dist[u] + w < dist[v])
                dist[v] = -INF;

    return dist;
}

int main() {
    int n, m, src;
    cin >> n >> m >> src;
    vector<Edge> edges(m);
    for (auto& [u, v, w] : edges) cin >> u >> v >> w;
    auto dist = bellman_ford(n, src, edges);
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) cout << "INF\n";
        else if (dist[i] == -INF) cout << "-INF\n";
        else cout << dist[i] << "\n";
    }
}

Version 3 -- SPFA (Shortest Path Faster Algorithm)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

// Returns dist array. Returns empty vector if negative cycle detected.
vector<ll> spfa(int n, int src, vector<vector<pair<int,ll>>>& adj) {
    vector<ll> dist(n, INF);
    vector<int> cnt(n, 0);       // count of times vertex enters queue
    vector<bool> inq(n, false);  // is vertex currently in queue?
    queue<int> q;

    dist[src] = 0;
    q.push(src);
    inq[src] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        for (auto& [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                    cnt[v]++;
                    // If a vertex enters the queue N times, negative cycle exists
                    if (cnt[v] >= n) return {};
                }
            }
        }
    }
    return dist;
}

int main() {
    int n, m, src;
    cin >> n >> m >> src;
    vector<vector<pair<int,ll>>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    auto dist = spfa(n, src, adj);
    if (dist.empty()) {
        cout << "Negative cycle detected\n";
        return 0;
    }
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) cout << "INF\n";
        else cout << dist[i] << "\n";
    }
}

---

Operations Reference

Operation	Time	Space
Standard Bellman-Ford	$O(VE)$	$O(V+E)$
Bellman-Ford with early termination	$O(VE)$ worst, often faster	$O(V+E)$
Negative cycle detection	$O(VE)$	$O(V+E)$
Full $-\mathrm{\infty }$ propagation	$O(VE)$ (extra $V-1$ rounds)	$O(V+E)$
SPFA (average case)	$O(E)$ to $O(kE)$, $k$ small	$O(V+E)$
SPFA (worst case)	$O(VE)$	$O(V+E)$
Shortest path with $\le k$ edges	$O(kE)$	$O(V+E)$

---

Problem Patterns & Tricks

Pattern 1 -- Negative Cycle Detection

Detect whether a negative-weight cycle exists in the graph. Run $V-1$ rounds of Bellman-Ford, then check if any edge still relaxes on round $V$.

Variant: Find a vertex on the cycle. Track the parent array during relaxation. If vertex $v$ relaxes on round $V$, walk back $V$ times through parent[] to land on a vertex guaranteed to be on the cycle, then trace the cycle.

Problems: CF 20B -- Equation, CSES -- Cycle Finding

Pattern 2 -- Currency Arbitrage

Given exchange rates between currencies, determine if you can start with some currency and end up with more of it. Model as a graph: each currency is a node, each exchange rate is a directed edge. Take $-\log (\text{rate})$ as edge weight -- a negative cycle in log-space means the product of rates exceeds 1 (profit).

Key insight: Bellman-Ford detects this negative cycle directly.

Problems: CF 1915G -- Bicycles, classic "arbitrage" problems on various OJs

Pattern 3 -- Shortest Path with at Most $k$ Edges

Stop Bellman-Ford after exactly $k$ rounds instead of $V-1$. After round $k$, dist[v] is the shortest path from source to $v$ using at most $k$ edges.

Important: Use a copy of the dist array from the previous round when relaxing (don't update in-place), otherwise you may use more than $k$ edges in a single round.

// k-edge-limited Bellman-Ford
vector<ll> dist(n, INF);
dist[src] = 0;
for (int i = 0; i < k; i++) {
    auto old = dist; // snapshot previous round
    for (auto& [u, v, w] : edges)
        if (old[u] < INF)
            dist[v] = min(dist[v], old[u] + w);
}

Problems: CF 229B -- Flights, CSES -- Flight Routes

Pattern 4 -- System of Difference Constraints

Given constraints of the form $x_j-x_i\le w_{ij}$, model as a graph: edge from $i$ to $j$ with weight $w_{ij}$. Run Bellman-Ford from a virtual source (connected to all nodes with weight 0). If a negative cycle exists, the system is infeasible. Otherwise, dist[v] gives a feasible assignment.

Problems: CF 1473E -- Minimum Path

Pattern 5 -- Bellman-Ford on Modified Graphs

Sometimes the graph is transformed before running Bellman-Ford: negate all weights (longest path becomes shortest path), add virtual nodes, or duplicate nodes for state-based shortest paths (e.g., "shortest path using at most $k$ special edges").

Layer graph trick: Create $k+1$ copies of the graph. An edge using a "special" operation goes from layer $i$ to layer $i+1$. Run Bellman-Ford on the layered graph.

Problems: CF 786B -- Legacy, CF 1204E -- Natasha, Sasha and the Prefix Sums

Pattern 6 -- Finding Longest Paths in DAGs via Bellman-Ford

Negate all edge weights, run Bellman-Ford, negate the result. Works even when Bellman-Ford isn't the optimal algorithm for DAGs (topological sort + DP is better), but useful when you already have Bellman-Ford in your template and the graph might not be a DAG.

Problems: CSES -- Longest Flight Route

Pattern 7 -- Reachability from Negative Cycles

After detecting which vertices are on negative cycles, BFS/DFS from those vertices to mark all reachable nodes as having $-\mathrm{\infty }$ distance. The "full propagation" version in the explained implementation handles this.

Problems: CF 855B -- Marvolo Gaunt's Ring, CSES -- High Score

---

Contest Cheat Sheet

+--------------------------------------------------------------+
|                  BELLMAN-FORD CHEAT SHEET                     |
+--------------------------------------------------------------+
| WHEN TO USE:                                                 |
|  - Shortest path with negative edge weights                  |
|  - Detect / find negative cycles                             |
|  - Shortest path with at most K edges                        |
|  - System of difference constraints                          |
|  - Graph too weird for Dijkstra (negative weights)           |
+--------------------------------------------------------------+
| CORE LOOP:                                                   |
|   for (int i = 0; i < n-1; i++)                             |
|     for (auto& [u,v,w] : edges)                             |
|       if (dist[u]<INF && dist[u]+w<dist[v])                 |
|         dist[v] = dist[u]+w;                                |
+--------------------------------------------------------------+
| NEG CYCLE: run 1 more round. If any edge relaxes -> cycle.  |
| K-EDGE:    run exactly K rounds with snapshot copy.          |
| SPFA:      queue-based, avg O(E), worst O(VE). Watch TLE.   |
+--------------------------------------------------------------+
| COMPLEXITY:  Time O(VE)  |  Space O(V+E)                    |
| INF VALUE:   1e18 (long long). NOT 1e9 (too small).         |
| GUARD:       Always check dist[u] < INF before relaxing.    |
+--------------------------------------------------------------+

---

Gotchas & Debugging

1. INF too small. If INF = 1e9 and edge weights are up to ${10}^9$, then INF + w overflows or looks like a valid distance. Use INF = 1e18 with long long.

2. Missing dist[u] < INF guard. Without it, relaxing from an unreachable vertex: INF + (-5) produces a huge positive number that looks "less than INF" due to overflow. Always guard.

3. In-place update in $k$-edge problems. If you update dist[] in-place, a single round can effectively use multiple edges. Use auto old = dist; and relax from old.

4. 0-indexed vs 1-indexed. If vertices are 1-indexed, dist needs size n+1 and loop i < n (not i < n-1).

5. Directed vs undirected. Each undirected edge is two directed edges. Don't forget to add both.

6. SPFA negative cycle detection. Checking cnt[v] >= n is correct but slow if the cycle is far from the source. Some implementations check for total relaxation count instead.

7. Not propagating $-\mathrm{\infty }$ fully. A single extra round only marks vertices directly on the cycle. Vertices reachable from the cycle also have $-\mathrm{\infty }$ distance. Run $V-1$ extra rounds or BFS/DFS from affected vertices.

8. Forgetting dist[src] = 0. Everything stays at INF. No relaxation happens. Silent wrong answer.

9. Multi-source Bellman-Ford. To run from multiple sources, set dist[s] = 0 for each source $s$ before the main loop. Don't run separate Bellman-Ford instances.

Mental Traps

Trap 1: "SPFA is fast -- I'll use it by default."

SPFA (Bellman-Ford with a queue) has $O(E)$ average-case but $O(VE)$ worst-case complexity. Codeforces problem setters routinely add anti-SPFA test cases that force worst-case behavior.

  Your mental model:                   Reality on CF:

  "SPFA is like fast BFS"             Adversarial graph forces re-queuing:

  Fast path:                              0 --> 1 --> 2 --> ... --> n-1
    0 -> 1 -> 2 -> ... -> t               |     |     |              ^
    queue: [0] [1] [2] ... done            |     |     |              |
    Each node queued ~1 time.              +-----+-----+--> ... ------+
                                           (back-edges with weights
  Expected: O(E)                            that trigger re-relaxation)

                                       Actual: O(VE) --> TLE

If the problem has non-negative weights, use Dijkstra. If it has negative weights and $n\cdot m\le {10}^7$, use standard Bellman-Ford. SPFA is a gamble.

Trap 2: "I detected a negative cycle -- now I know the answer."

Detection is step 1. The hard part is reasoning about reachability.

  Graph where detection alone is NOT enough:

       +---(-3)---+
       |          |
  s -> A -> B -> C -> D -> t
            |         ^
            +---(5)---+

  Negative cycle: A -> B -> C -> A (total weight < 0)

  Questions requiring MORE than detection:
    Q: "Is d[t] = -INF?"
       --> Only if t is reachable FROM a cycle node.
       --> C -> D -> t: yes, t is reachable from cycle.
       --> So d[t] = -INF.

    Q: "What if t is connected only from s directly?"
       s -> t  (direct edge, weight 10)
       s -> A -> B -> C -> A -> ... (cycle, but can't reach t)
       --> t is NOT reachable from the cycle.
       --> d[t] = 10, NOT -INF.
       --> Detection alone wrongly suggests "negative cycle = all bets off."

After detecting which nodes are on a negative cycle (relaxed in round $n$), BFS/DFS from those nodes to find all reachable vertices. Only those vertices have $d[v]=-\mathrm{\infty }$.

---

Self-Test

• [ ] I can write Bellman-Ford from memory (n-1 rounds, edge iteration, relaxation)
• [ ] I can explain why n-1 rounds suffice using the "max edges in shortest path" argument
• [ ] I can describe the negative cycle detection step (what the n-th round checks and why improvement implies a cycle)
• [ ] I can state why Dijkstra fails on negative edges (the greedy "finalize on pop" invariant breaks)
• [ ] I can name one problem type requiring Bellman-Ford (negative edges) and one where Dijkstra is strictly better (non-negative weights, larger n)

---

Practice Problems

CF Rating	What You Should Be Comfortable With
1200	Basic Bellman-Ford, detect if negative cycle exists
1500	Extract the actual negative cycle, shortest path with at most $k$ edges, SPFA
1800	Bellman-Ford on modified graphs (negated weights for longest path), arbitrage problems, layered BF
2100	Johnson's algorithm (BF for potentials + Dijkstra), BF with constraints (difference constraints), SPFA anti-hack awareness

#	Problem	Source	Difficulty	Key Idea
1	Shortest Routes I	CSES	Easy	Basic SSSP (warm-up, use Dijkstra or BF)
2	High Score	CSES	Medium	Longest path, negate weights, detect neg cycles
3	Cycle Finding	CSES	Medium	Find and output an actual negative cycle
4	CF 20B -- Equation	CF	Medium	Negative cycle detection in small graph
5	CF 1473E -- Minimum Path	CF ~2000	Medium-Hard	Shortest path with modified edge weights
6	CF 1915G -- Bicycles	CF ~1900	Medium-Hard	State-based shortest path
7	CF 229B -- Flights	CF ~1800	Medium	Path counting with edge constraints
8	Flight Discount	CSES	Medium	Layered graph / $k$-edge trick
9	CF 786B -- Legacy	CF ~2200	Hard	Segment-tree-based graph + shortest path

---

Common Mistakes

1. Modifying dist in-place for "$k$-edge shortest path." You implement "shortest path with at most $k$ edges" using Bellman-Ford, but get shorter paths than expected -- paths using more than $k$ edges:

   for (int i = 0; i < k; i++) {
       for (auto [u, v, w] : edges) {
           if (dist[u] + w < dist[v]) {
               dist[v] = dist[u] + w;  // BUG: modifying dist in-place
           }
       }
   }

   When you update dist[v] during round $i$, another edge in the same round can use the updated dist[v], effectively using $i+1$ or more edges. Fix: copy the distance array at the start of each round and relax from the copy: new_dist[v] = min(new_dist[v], old_dist[u] + w).

Debug Drills

Drill 1. Bellman-Ford reports a negative cycle that doesn't exist:

vector<long long> dist(n + 1, 1e18);
dist[src] = 0;
for (int i = 0; i < n - 1; i++)
    for (auto [u, v, w] : edges)
        if (dist[u] + w < dist[v])
            dist[v] = dist[u] + w;
// Check for negative cycle:
for (auto [u, v, w] : edges)
    if (dist[u] + w < dist[v])
        cout << "Negative cycle!";

What's wrong?

If dist[u] is 1e18 (unreachable), then dist[u] + w might still be a huge number that's less than dist[v] = 1e18 due to floating-point or integer arithmetic. Fix: add the check if (dist[u] != 1e18 && dist[u] + w < dist[v]) -- only relax from reachable nodes.

Drill 2. SPFA runs forever (infinite loop):

queue<int> q;
vector<bool> in_queue(n + 1, false);
dist[src] = 0;
q.push(src);
in_queue[src] = true;
while (!q.empty()) {
    int u = q.front(); q.pop();
    in_queue[u] = false;
    for (auto [v, w] : adj[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            if (!in_queue[v]) {
                q.push(v);
                in_queue[v] = true;
            }
        }
    }
}

What's wrong?

If there's a negative cycle reachable from src, SPFA will loop forever because nodes in the cycle keep getting re-enqueued with shorter distances. Fix: count how many times each node is enqueued. If any node is enqueued more than $V-1$ times, a negative cycle exists -- break and report it.

Drill 3. Bellman-Ford gives wrong shortest path on this graph:

// Edges: (1->2, w=-1), (2->3, w=-1), (3->1, w=-1), (1->4, w=1)
// Source: 1, Query: dist[4]
// Expected: 1, but code returns a very negative number

What's wrong?

Node 1 is part of a negative cycle (1->2->3->1 with total weight -3). After $V-1=3$ iterations, the distance to node 1 keeps decreasing, which then decreases the distance to node 4 as well. The shortest path to node 4 is $-\mathrm{\infty }$ because you can loop around the negative cycle any number of times before going to 4. The code should detect that node 4 is "affected by a negative cycle" and report accordingly.

---

Further Reading

• cp-algorithms -- Bellman-Ford -- thorough writeup with proofs and code.
• cp-algorithms -- Finding negative cycle -- specifically on extracting the cycle.
• CF Blog -- SPFA is dead -- why SPFA gets killed by anti-SPFA test cases.
• CSES Problem Set -- Graph Algorithms -- excellent practice set for shortest path variants.
• See: Dijkstra for non-negative-weight SSSP.
• See: Floyd-Warshall for all-pairs shortest paths.

---