Bellman-Ford algorithm — DP approach, negative cycles detection, O(VE): Question bank

Before we start, here is a fully self-contained refresher — the whole algorithm plus its vocabulary — so no question below forces you to click away.

Formula The initialization and the whole loop, inline

Start every distance as "unknown / infinitely far," except the source which costs $0$ to reach: $dist [s] = 0, dist [v] = \infty (v \neq = s)$ Then relax all $E$ edges, $V - 1$ times, and do one extra pass to detect negative cycles:

def bellman_ford(V, edges, src):
    dist = [float('inf')] * V     # everything unknown ...
    dist[src] = 0                 # ... except the source costs 0
    for _ in range(V - 1):        # V-1 relaxation passes
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:           # a whole pass changed nothing -> stop
            break
    for u, v, w in edges:         # ONE extra pass = detection
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None           # a reachable negative cycle exists
    return dist

Keep this snippet in view: most traps below are about one line of it.

The figures below show what "relaxation," "pass-by-pass convergence," and "detection" actually look like — glance at them before diving into the traps.

Edge relaxation, one step:

Figure — Bellman-Ford algorithm — DP approach, negative cycles detection, O(VE)

Pass-by-pass convergence on a small graph:

Why the extra pass catches a negative cycle:

True or false — justify

Every answer explains why, never a bare verdict.

Bellman-Ford needs exactly

V - 1

passes to always be correct on a graph with no negative cycle.

True. A simple shortest path visits at most

V

vertices, so it uses at most

V - 1

edges; each pass "locks in" at least one more edge of that path, so

V - 1

passes suffice.

If a pass makes no updates, the algorithm can stop early even if fewer than

V - 1

passes have run.

True. No update means every dist[] value already satisfies all relaxation conditions, so further passes cannot change anything — that is the early-exit optimization (the if not updated: break line).

Running

V

passes instead of

V - 1

gives more accurate distances.

False. Distances converge by pass

V - 1

; the

V

-th pass only detects negative cycles. If it changes a distance, that value is inside a negative cycle and is meaningless, not "more accurate."

Bellman-Ford can compute shortest paths on a graph that contains a negative cycle unreachable from the source.

True. Only cycles reachable from

s

corrupt distances. An unreachable negative cycle never touches any relaxed dist[] value, so the answers for reachable nodes stay correct.

Bellman-Ford finds every negative cycle in the graph.

False. It only reports negative cycles reachable from the source

s

. A negative cycle in a disconnected part stays invisible unless you add a virtual source with

0

-weight edges to all vertices.

The final distance array does not depend on the order in which edges are relaxed within a pass.

True for the final result after

V - 1

passes; the intermediate per-pass values do depend on order, but convergence to the same answer is guaranteed.

Bellman-Ford works on undirected graphs with a single negative edge.

False (in general). An undirected negative edge

u - v

is really two directed edges

u \to v

and

v \to u

of the same negative weight — together they form a negative cycle of length 2, which Bellman-Ford will flag.

Dijkstra could replace Bellman-Ford if we just add a big constant to every edge weight to make them non-negative.

False. Adding a constant

c

to each edge penalizes paths by

c \times (number of edges)

, so it changes which path is shortest. Longer-hop paths get unfairly inflated; the answers become wrong. (Dijkstra's greedy "finalize the closest node" trick — see Dijkstra's Algorithm — needs the original non-negative weights, not doctored ones.)

The dist[u] != inf guard changes which final distances Bellman-Ford produces.

False in exact arithmetic — inf + w stays inf, so relaxing from an unreachable node never helps. The guard exists to avoid overflow in fixed-width integers and spurious "updates," not to change correctness.

If the graph is a DAG (no cycles at all), Bellman-Ford can never report a negative cycle.

True. A negative cycle is a cycle; a DAG has none by definition, so the extra pass can never find an improving edge. (A topological-order relaxation would be faster here, but Bellman-Ford is still correct.)

Spot the error

Each line describes a buggy claim or code idea; the reveal names the exact flaw.

"I return dist immediately after

V - 1

passes without the extra pass."

You lose negative-cycle detection. If a reachable negative cycle exists, the returned distances are finite garbage instead of a "no shortest path" flag.

"I do the detection pass, and if an edge relaxes I set dist[v] to the new smaller value and continue."

Wrong: once you know a negative cycle exists, distances are undefined. You should report the cycle (return None/flag), not keep shrinking values that will never stabilize.

"I only run the detection pass over edges I updated in pass

V - 1

Buggy. A negative cycle may only reveal itself through an edge you did not touch last pass; the detection pass must scan all

E

edges.

"I initialize dist[src] = 0 and everything else to 0 too."

Wrong base case. Non-source nodes must start at

\infty

, meaning "unknown / unreachable so far." Starting at

0

pretends every node is free to reach and corrupts all relaxations.

"I break out of the loop the first time any single edge cannot be improved (its relax check is false)."

Wrong condition. You break only when an entire pass improves nothing. A single edge whose dist[u]+w < dist[v] check fails says nothing; other edges in the same pass may still improve — that is why the code tracks an updated flag over the whole sweep.

"To speed things up I relax each edge only if its endpoint changed last pass — that's the whole optimization."

That describes SPFA, a queue-based refinement that only re-processes vertices whose distance just dropped. It is a valid optimization but it is not plain Bellman-Ford, and its worst case is still

O (V E)

; do not claim it changes the guarantee.

"For an all-pairs shortest path I run Bellman-Ford once and read off all distances."

Error: one Bellman-Ford run is single-source — distances from one

s

only. For all pairs, run it

V

times (once per source) or use Floyd-Warshall, which computes every pair in

O (V^{3})

"My graph has a positive cycle, so the extra pass will falsely report a negative cycle."

False alarm about a false alarm. A positive (or zero) cycle never lowers a distance, so the detection pass finds no improving edge and correctly reports "no negative cycle."

Why questions

Why is the loop bounded by

V - 1

and not by

E

(the number of edges)?

Because the bound comes from path length, not edge count. A simple shortest path has at most

V - 1

edges regardless of how many edges

E

the graph has, so

V - 1

passes always suffice.

Why does one successful relax in the

V

-th pass prove a negative cycle exists?

After

V - 1

passes every simple path is fully accounted for, so nothing simple can improve. Any further improvement must come from re-visiting a vertex — a cycle — and only a negative cycle lowers the total, so an improving edge is a certificate of one.

Why does Bellman-Ford make "no greedy commitment," unlike Dijkstra?

Dijkstra permanently finalizes the closest unfinished node, trusting that no future path beats it — valid only for non-negative edges. Bellman-Ford never finalizes; it keeps re-relaxing every edge, so a later negative edge can still rescue a distance.

Why is Bellman-Ford considered Dynamic Programming rather than greedy?

Its state

D [k] [v]

= shortest distance to

v

using at most

k

edges, built from

D [k - 1]

via a recurrence. It solves overlapping subproblems bottom-up over the number of edges — the definition of DP.

Why does adding a "virtual source" connected to every vertex with

0

-weight edges let us detect all negative cycles?

The virtual source makes every vertex reachable, so every negative cycle is now reachable from a single source. One Bellman-Ford run from the virtual source then flags any negative cycle in the whole graph, connected or not.

Why must we guard relaxation with dist[u] != inf?

An unreachable

u

has dist[u] = inf. In integer arithmetic inf + w can overflow to a negative-looking number, which would fake an improvement and corrupt dist[v]. The guard skips these impossible relaxations.

Why is the time complexity

O (V \cdot E)

and not

O (V^{2})

We do up to

V - 1

passes, and each pass relaxes all

E

edges once:

(V - 1) \times E

work. It is written in terms of

E

because a graph can have anywhere from

V - 1

V^{2}

edges.

Edge cases

Single vertex, no edges, source = that vertex.

dist = [0]. With

V = 1

we run

V - 1 = 0

relaxation passes; the base case is already the final answer. The detection pass finds nothing.

Source cannot reach some vertex

t

dist[t] stays

\infty

forever — correct. "Unreachable" is faithfully represented by an unchanged infinite distance, and the guard keeps us from ever relaxing out of it.

A graph with a self-loop

v \to v

of weight

- 2

This is a negative cycle of length 1. If

v

is reachable, the detection pass relaxes the self-loop endlessly and correctly reports a negative cycle.

A graph with a self-loop

v \to v

of weight

+ 3

Harmless. A positive self-loop never improves dist[v], so it is silently ignored and never triggers detection.

Two vertices with edges

u \to v (w)

and

v \to u (- w)

for the same

w > 0

The round trip sums to

w + (- w) = 0

: a zero-weight cycle, not negative. Distances converge normally and no cycle is reported — negativity, strictly less than zero, is what matters.

All edge weights are non-negative.

Bellman-Ford still produces the correct answer, just slower than Dijkstra's Algorithm. There can be no negative cycle, so the detection pass always passes clean.

The shortest path genuinely uses all

V - 1

edges (a long chain).

This is the worst case that requires every one of the

V - 1

passes. With an unlucky edge order, each pass may extend the frontier by only one edge, so you cannot safely stop early.

Empty edge list but

V > 1

Only the source has a finite distance (

0

); all others stay

\infty

. No edge means nothing to relax and nothing to detect — trivially correct.

Recall One-question self-audit

Cover the reveals above. If you can restate why the $V$ -th pass computes nothing but only detects, and why only reachable cycles are found, you have understood the two ideas this bank keeps circling. This is one corner of the broader Shortest Path Problem.

Connections

Dijkstra's Algorithm — the greedy method these traps contrast against
Dynamic Programming — why Bellman-Ford is DP over edge count
Floyd-Warshall — the all-pairs cousin
Shortest Path Problem
Negative Weight Cycles
Graph Relaxation
SPFA