Bellman Ford Algorithm

Hard

Relax all edges V-1 times; handles negatives

Problem

Find shortest paths from a source allowing negative edges, and detect negative cycles.

In simple words

Relax every edge n-1 times; this works even with negative weights (and can flag negative cycles).

The idea

Bellman-Ford makes no greedy pick — it simply relaxes every edge, V-1 times. Why V-1? A shortest path uses at most V-1 edges, and each full sweep locks in one more edge of every shortest path. It is slower than Dijkstra (O(V·E)) but copes with negative weights, and if a V-th sweep still improves something, a negative cycle exists.

The trick

V−1 rounds is enough: a shortest path has at most V−1 edges, and every sweep fixes one more of them.
If a distance still drops on an extra V-th sweep, a negative cycle exists.

←→stepspaceplay

dist[0, ∞, ∞, ∞]

1/9

Optimal

timeO(V*E)spaceO(V)

1dist[src] = 0, all others = ∞2repeat V-1 times:3  for each edge (u → v, w): if dist[u] + w < dist[v]: dist[v] = dist[u] + w4one more improving pass ⇒ a negative cycle exists

Input

nodes: 4, 5 edges

Memory

dist: [0, ∞, ∞, ∞]
round: —

Output

shortest dist: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n=5, edges=[[0,1,-1],[0,2,4],[1,2,3],[1,3,2],[1,4,2],[3,2,5],[3,1,1],[4,3,-3]], src=0
Output:: [0, -1, 2, -2, 1]
Explanation:: Handles negative edges Dijkstra can't.

Example 2

Input:: n=2, edges=[[0,1,5]], src=0
Output:: [0, 5]
Explanation:: 0→1 costs 5.

Example 3

Input:: n=3, edges=[[0,1,4],[0,2,5],[1,2,-2]], src=0
Output:: [0, 4, 2]
Explanation:: 0→1→2 (2) beats direct 5.

Practice this problem:LeetCode(opens in a new tab)GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.