Pattern #59

Bellman-Ford Algorithm

Repeated edge relaxation, negative weights and cycles, limited-edge shortest paths, early stopping, reachability details, and Go templates.

Must Solve

10 core questions — solve these first.

1.Bellman-Ford Shortest Path
Relax all edges V − 1 timesmedium
2.Detect Negative Cycle in Graph
One extra successful round detects itmedium
3.Cheapest Flights Within K Stops
Limit relaxation rounds and copy distancesmedium
4.Network Delay Time — Compare with Dijkstra
Non-negative weights usually favor Dijkstramedium
5.Shortest Path with Negative Weights
Bellman-Ford handles negative edgesmedium
6.Currency Arbitrage — Concept
Log conversion reveals profitable negative cyclehard
7.Difference Constraints — Concept
Inequalities become weighted directed edgeshard
8.Find the City With Smallest Number of Neighbors
Compare all-pairs alternativesmedium
9.Shortest Path in Directed Weighted Graph
Edge list is the natural representationmedium
10.Negative Cycle Reachability Problems
Only source-reachable cycles affect source pathshard

Also Important

5 advanced relations and optimizations.

11.Bellman-Ford with Path Reconstruction
Store parent on improvementmedium
12.Bellman-Ford with Early Stopping
Stop when a full pass makes no updateeasy
13.Shortest Path with Maximum Number of Edges
Rounds bound allowed edge counthard
14.SPFA — Practical Variant
Queue-based heuristic; poor worst casehard
15.Johnson's Algorithm — Advanced Relation
Reweight with Bellman-Ford, then run Dijkstrahard

How to Think

Negative edge exists?Bellman-Ford

Need negative-cycle detection?Relax one extra round

At most K edges or stops?Limit the number of rounds

All weights non-negative?Usually prefer Dijkstra

Relax ALL edges
↓
Repeat V − 1 times
↓
One extra round
↓
Any reachable improvement = negative cycle

Go Quick Reference — Bellman-Ford

type Edge struct { from, to int; weight int64 }

func bellmanFord(n int, edges []Edge, start int) ([]int64, bool) {
    dist := make([]int64, n)
    for i := range dist { dist[i] = INF }
    dist[start] = 0
    for round := 1; round < n; round++ {
        changed := false
        for _, e := range edges {
            if dist[e.from] == INF { continue }
            cand := dist[e.from] + e.weight
            if cand < dist[e.to] { dist[e.to], changed = cand, true }
        }
        if !changed { break }
    }
    for _, e := range edges {
        if dist[e.from] != INF && dist[e.from]+e.weight < dist[e.to] {
            return dist, true
        }
    }
    return dist, false
}

A shortest simple path uses at most V − 1 edges, so each full pass can propagate correct distance information one edge farther.

Key Variants

K Stops

Copy the previous distance array each round so one round cannot accidentally use multiple new edges. K stops permits K + 1 edges.

Negative Cycle Reachability

For source shortest paths, relax only from reachable nodes. A disconnected negative cycle does not affect the source.

Path Reconstruction

Update parent[v] whenever dist[v] improves; do not report a finite shortest route through an affected negative cycle.

Bellman-Ford as DP

After round i, distances represent best paths using at most i edges—exactly the state behind limited-flight problems.

Visual Memory Rule

Relax ALL edges → one round
Repeat V − 1 rounds → shortest simple paths
No update → stop early
One more improvement → reachable negative cycle

Complexity

Time:  O(VE)
Space: O(V)
Edge list storage: O(E)
Early stopping: often faster, worst case remains O(VE)

Common Interview Mistakes

• Forgetting the dist[u] != INF reachability guard

• Running only one edge pass

• Skipping the extra negative-cycle pass

• Miscounting K stops versus K + 1 edges

• Updating in place when rounds must limit edges

• Treating every negative cycle as source-relevant

• Using Bellman-Ford on a DAG instead of topological relaxation

Interview Rules

Negative edge       → Bellman-Ford
Normal rounds       → V − 1
Negative cycle      → improvement on extra round
Unreachable node    → never relax from INF
At most K edges     → K copied rounds
No update in a pass → stop early
DAG                 → topological shortest path

Production Thinking

Discounts and credits → negative edges model rebates without implying a negative cycle.

Currency arbitrage → -log(rate) turns profitable cycles into negative cycles.

Production warning → O(VE) is expensive; prefer Dijkstra for non-negative weights or topological relaxation for DAGs.

Remember This

Bellman-Ford → negative edges
Representation → edge list
Rounds → V − 1
Extra round → negative cycle
Reachability guard → dist[u] != INF
Early stop → no update
Time → O(VE)

💡 Golden Rule: Relax every edge repeatedly; if a reachable distance still improves after V − 1 rounds, a negative cycle is present.