Bellman-Ford Algorithm
Last updated
Bellman-Ford finds the shortest path from a source node to every other node, and unlike Dijkstra it works even when some edge weights are negative. It works by brute-force relaxation: it repeatedly scans every edge and, if going through that edge gives a shorter distance, it updates the target's distance. Press play above to watch the tentative distances drop pass by pass.
After V - 1 passes over all edges, every shortest path (which can have at most V - 1 edges) has been found. This makes it O(V · E) - slower than Dijkstra, but it handles negative weights and can detect a negative-weight cycle (if a V-th pass still relaxes an edge, no shortest path exists).
Time & space complexity
| Measure | Complexity | Notes |
|---|---|---|
| Time | O(V · E) | V − 1 passes over all E edges |
| Space | O(V) | One distance per node |
| Negative weights | Supported | Its key advantage over Dijkstra |
| Negative cycles | Detectable | A relaxing V-th pass signals one |
Step by step
| Step | What happens |
|---|---|
| 1 | Set the source distance to 0 and all others to infinity. |
| 2 | Repeat the next step V − 1 times. |
| 3 | For every edge (u → v, w), check if dist[u] + w < dist[v]. |
| 4 | If so, relax it: set dist[v] = dist[u] + w. |
| 5 | Stop early if a full pass makes no change. |
Worked example
Source S on 4 nodes S, A, B, C with edges S→A (4), S→B (5), A→C (3), B→A (-3), relaxed in that order. Distances start at S=0 and everything else ∞:
| Pass | Distances [S, A, B, C] | Action |
|---|---|---|
| Init | [0, ∞, ∞, ∞] | Source distance is 0, all others infinity. |
| 1 | [0, 2, 5, 7] | Relax S→A to 4, S→B to 5, A→C to 7, then B→A lowers A to 5 + (-3) = 2. |
| 2 | [0, 2, 5, 5] | A→C now improves C to 2 + 3 = 5; no other edge relaxes. |
| 3 | [0, 2, 5, 5] | No edge relaxes, so distances are final: A costs 2 via S→B→A. |
When to use Bellman-Ford
| Use it when | Avoid it when |
|---|---|
| Edge weights can be negative. | All weights are non-negative (Dijkstra is faster). |
| You must detect negative-weight cycles. | The graph is huge and dense - O(V · E) is too slow. |
| The graph is small or sparse. | You only need a single source-to-target query on a big graph. |
| You need a simple, easy-to-implement baseline. | Weights are non-negative and latency matters. |
Bellman-Ford Algorithm code
A clean, runnable Bellman-Ford Algorithm implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Bellman-Ford Algorithm code in Python
Python
1def bellman_ford(vertices, edges, start):2 dist = {v: float("inf") for v in vertices}3 dist[start] = 04 # Relax every edge V-1 times5 for _ in range(len(vertices) - 1):6 for u, v, w in edges:7 if dist[u] + w < dist[v]:8 dist[v] = dist[u] + w9 # One more pass: any improvement means a negative cycle10 for u, v, w in edges:11 if dist[u] + w < dist[v]:12 raise ValueError("Graph contains a negative-weight cycle")13 return dist14
15
16vertices = ["A", "B", "C", "D", "E"]17edges = [18 ("A", "B", 6), ("A", "C", 7), ("B", "D", 5), ("B", "E", -4),19 ("C", "D", -3), ("D", "B", -2), ("E", "D", 7),20]21
22for node, d in bellman_ford(vertices, edges, "A").items():23 print(f"A -> {node}: {d}")Bellman-Ford Algorithm code in JavaScript
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 6], ["A", "C", 7], ["B", "D", 5], ["B", "E", -4],4 ["C", "D", -3], ["D", "B", -2], ["E", "A", 2],5];6
7function bellmanFord(source) {8 const dist = Object.fromEntries(nodes.map((n) => [n, Infinity]));9 dist[source] = 0;10 // Relax every edge V-1 times11 for (let i = 0; i < nodes.length - 1; i++) {12 for (const [u, v, w] of edges) {13 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;14 }15 }16 // One more pass: any improvement means a negative cycle17 for (const [u, v, w] of edges) {18 if (dist[u] + w < dist[v]) throw new Error("Negative cycle detected");19 }20 return dist;21}22
23console.log("Shortest distances from A:", bellmanFord("A"));Bellman-Ford Algorithm code in Java
Java
1import java.util.Arrays;2
3public class Main {4 public static void main(String[] args) {5 int n = 5;6 // Directed edges {from, to, weight}; negative weights allowed7 int[][] edges = {8 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {1, 2, 8},9 {2, 4, 9}, {3, 1, -2}, {4, 3, 7}, {2, 3, -3}10 };11 int[] dist = new int[n];12 Arrays.fill(dist, Integer.MAX_VALUE);13 dist[0] = 0;14
15 // Relax every edge V-1 times16 for (int i = 0; i < n - 1; i++) {17 for (int[] e : edges) {18 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {19 dist[e[1]] = dist[e[0]] + e[2];20 }21 }22 }23
24 // One more pass: any improvement means a negative cycle25 boolean hasNegativeCycle = false;26 for (int[] e : edges) {27 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {28 hasNegativeCycle = true;29 }30 }31
32 System.out.println("Distances from 0: " + Arrays.toString(dist));33 System.out.println("Negative cycle: " + hasNegativeCycle);34 }35}Bellman-Ford Algorithm code in C++
C++
1#include <iostream>2#include <vector>3
4struct Edge {5 int from, to, weight;6};7
8int main() {9 const int INF = 1000000000;10 const int n = 5;11 std::vector<Edge> edges = {12 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},13 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},14 };15 std::vector<int> dist(n, INF);16 dist[0] = 0;17 // Relax every edge V-1 times18 for (int pass = 0; pass < n - 1; ++pass) {19 for (const Edge& e : edges) {20 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {21 dist[e.to] = dist[e.from] + e.weight;22 }23 }24 }25 // One extra pass: any improvement means a negative cycle26 bool negativeCycle = false;27 for (const Edge& e : edges) {28 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {29 negativeCycle = true;30 }31 }32 if (negativeCycle) {33 std::cout << "Negative cycle detected\n";34 } else {35 for (int v = 0; v < n; ++v) {36 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";37 }38 }39 return 0;40}Bellman-Ford Algorithm code in C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7typedef struct {8 int from, to, weight;9} Edge;10
11int main(void) {12 Edge edges[] = {13 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},14 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},15 };16 int m = sizeof(edges) / sizeof(edges[0]);17 int dist[N];18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // Relax every edge V-1 times21 for (int pass = 0; pass < N - 1; pass++) {22 for (int i = 0; i < m; i++) {23 Edge e = edges[i];24 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {25 dist[e.to] = dist[e.from] + e.weight;26 }27 }28 }29 // One extra pass: any improvement means a negative cycle30 bool negativeCycle = false;31 for (int i = 0; i < m; i++) {32 Edge e = edges[i];33 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {34 negativeCycle = true;35 }36 }37 if (negativeCycle) {38 printf("Negative cycle detected\n");39 } else {40 for (int v = 0; v < N; v++) {41 printf("Distance 0 -> %d: %d\n", v, dist[v]);42 }43 }44 return 0;45}Bellman-Ford FAQ
What is the time complexity of Bellman-Ford?
Bellman-Ford runs in
O(V · E) time: it makes V - 1 passes, and each pass relaxes all E edges. That is slower than Dijkstra's O((V + E) log V), which is the price of supporting negative edge weights.When should I use Bellman-Ford instead of Dijkstra?
Use Bellman-Ford when the graph can have negative edge weights, or when you need to detect negative-weight cycles. Dijkstra is faster but only correct with non-negative weights. A common real use is currency-exchange arbitrage detection, where negative cycles matter.
How does Bellman-Ford detect a negative cycle?
After the
V - 1 relaxation passes, all shortest paths are finalized if no negative cycle exists. If one more pass can still relax an edge, then a negative-weight cycle is reachable, and shortest paths are undefined (you could loop forever to lower the cost).What is the difference between Bellman-Ford and Floyd-Warshall?
Bellman-Ford computes shortest paths from a single source in
O(V · E), while Floyd-Warshall computes all-pairs shortest paths in O(V³). On a dense graph, running Bellman-Ford from every source costs O(V² · E), so Floyd-Warshall is usually the better choice when you need every pair. Both handle negative edges and can flag negative cycles.Why does Bellman-Ford need exactly V - 1 passes?
Any shortest path in a graph with no negative cycle uses at most
V - 1 edges, because a path visiting more than V nodes must repeat one. Each pass guarantees at least one more edge of every shortest path is relaxed correctly, so V - 1 passes are enough to settle them all. A common misconception is that more passes improve the answer - they never do unless a negative cycle exists.Can Bellman-Ford stop early?
Yes. If a full pass over all edges relaxes nothing, every distance is already optimal and you can stop before reaching
V - 1 passes. This early-exit optimization often makes it much faster on graphs that converge quickly, though the worst-case bound stays O(V · E).Related resources
More visualizations
