Bellman-Ford Algorithm

Given a directed graph with V vertices (0 .. V-1) and edges edges[i] = [u, v, w] where the weight w may be negative, return the shortest distance from source 0 to every vertex. Use 100000000 for unreachable vertices. If the graph contains a negative-weight cycle, return [-1].

Hints

· Stuck? Reveal one nudge at a time.

Dijkstra fails with negative edges — use Bellman-Ford.

Relax all edges V-1 times; a shortest path has at most V-1 edges.

One more relaxable round means a negative cycle — return [-1].

Common doubts

A simple shortest path has at most V-1 edges, and each round extends correct distances by one edge, so V-1 rounds settle them all.

If a distance can still decrease after V-1 rounds, the path must loop through a negative cycle, decreasing without bound.

Relaxing from an unreachable vertex (value BIG) would create bogus distances; skip it.

Interview follow-ups

· What an interviewer asks next.

A queue-based variant only re-relaxes vertices whose distance changed, often much faster in practice.

Mark vertices relaxed in the V-th round and propagate; those reachable from them have undefined distance.

Fun facts

Bellman-Ford underlies distance-vector routing protocols like RIP.
It's one of the few shortest-path algorithms that tolerates negative edges.

Asked at

AmazonGoogleMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: V = 3, edges = [[0,1,4],[0,2,5],[1,2,-3]]
Output: [0, 4, 1]
0→1→2 (4 + -3 = 1) beats the direct 0→2 = 5.

Example 2

Input: V = 3, edges = [[0,1,1],[1,2,-1],[2,0,-1]]
Output: [-1]
The cycle 0→1→2→0 has total weight -1 — a negative cycle.

Constraints

- 1 <= V <= 500 - 0 <= edges.length <= V*(V-1) - -1000 <= w <= 1000 - edges are directed

Dijkstra can't handle negative edges; Bellman-Ford can. Its guarantee: relaxing all edges V-1 times settles every shortest path, because a shortest path in a graph with no negative cycle uses at most V-1 edges, and each round pushes correct distances one edge further.

Negative-cycle detection falls out for free: after V-1 rounds, do one more. If any edge can still be relaxed, some distance is decreasing without bound — a negative cycle — so return [-1]. O(V·E).

An easy optimization: if a whole round makes no change, the distances have converged and you can stop early (and there's no reachable negative cycle).

Prerequisites

Before you start

· Concepts used directly in the solution.

Edge relaxation. dist[v] = min(dist[v], dist[u] + w).

V-1 bound. a shortest path has ≤ V-1 edges.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Can weights be negative?”

Yes — that's why Bellman-Ford, not Dijkstra.

“What signals a negative cycle?”

A relaxation still possible after V-1 rounds.

The ideal opening — say it like this

I relax all edges V-1 times; that settles every shortest path since a path has at most V-1 edges.

One more round that still relaxes means a negative cycle, so I return [-1].

Understand the problem

Worked example — V = 3, edges [[0,1,4],[0,2,5],[1,2,-3]]

round 1: dist[1]=4, dist[2]=5, then via 1: dist[2]=4-3=1
no V-th improvement -> dist = [0, 4, 1]

Key observations

1Aha

V-1 rounds settle all shortest paths

A path has at most V-1 edges.

2Aha

A V-th improvement ⇒ negative cycle

Unbounded decrease means a negative loop.

3Aha

No-change round ⇒ converged

Safe to stop early.

Brute force vs optimal

	Full V-1 rounds	Early termination
Rounds	always V-1	stop when a round changes nothing
Time	O(V·E)	O(V·E) worst case, often less
Neg cycle	extra round check	extra round check

Both compute the same distances and detect the same negative cycles. Full code is in the Approaches selector below.

Summary

Key takeaway

Relax all edges V-1 times to settle shortest paths; a further relaxation signals a negative cycle (return [-1]). O(V·E), with an easy early-stop when a round makes no change.

repeat V-1 times: relax all edges
one more round relaxes anything? -> negative cycle -> [-1]