Loading algorithms…

Loading visualizer…

Algorithms/Graph/Bellman-Ford

Bellman-Ford

Single-source shortest paths that handle negative edge weights and detect negative-weight cycles.

GraphShortest PathDynamic ProgrammingNegative WeightsO(V·E)
Graph Visualization
A → G
1 / 0
Speed

⚖️ Why Bellman-Ford?

Dijkstra assumes every edge relaxes distance monotonically — once it marks a node as "final," it never revisits it. With negative weights, that assumption breaks. Bellman-Ford instead relaxes every edge V−1 times so cheaper paths can propagate through chains that Dijkstra would have ignored. Compare with Dijkstra →

bellman-ford.js
1function bellmanFord(graph, source, target) {
2 const dist = {};
3 const prev = {};
4 
5 // Initialize all distances to Infinity
6 for (const v of graph.nodes) {
7 dist[v] = Infinity;
8 prev[v] = null;
9 }
10 dist[source] = 0;
11 
12 // Relax all edges V-1 times
13 for (let i = 1; i <= V - 1; i++) {
14 let updated = false;
15 for (const [u, v, w] of graph.edges) {
16 if (dist[u] + w < dist[v]) {
17 dist[v] = dist[u] + w;
18 prev[v] = u;
19 updated = true;
20 }
21 }
22 if (!updated) break; // early-exit optimization
23 }
24 
25 // Check for negative-weight cycles
26 for (const [u, v, w] of graph.edges) {
27 if (dist[u] + w < dist[v]) {
28 return { hasNegativeCycle: true };
29 }
30 }
31 
32 return { dist, prev };
33}

Algorithm Explanation

Bellman-Ford is a single-source shortest-path algorithm that, unlike Dijkstra, handles negative edge weights and can detect negative-weight cycles.

⚙️ How It Works

  1. Initialize — Set the distance to the source as 0 and all other distances to ∞.
  2. Relax all edges V−1 times — For each edge (u, v, w), if dist[u] + w < dist[v], update dist[v] and record prev[v] = u.
  3. Early-exit optimization — If a full pass relaxes nothing, distances have stabilized and the algorithm can stop.
  4. Detect negative cycles — Run one more pass. If any edge can still be relaxed, a negative-weight cycle is reachable from the source.

🔑 Why V−1 Iterations?

A shortest path in a graph with no negative cycles visits at most V − 1 edges. Each iteration of the outer loop can lengthen the shortest known path by at most one edge, so V−1 iterations are sufficient to propagate the cheapest path to every node.

⚠️ Negative cycles: If the graph contains a cycle whose total weight is negative, you can keep walking around it forever to drive the distance to −∞. Bellman-Ford detects this in the V-th pass and reports that the shortest path is undefined.

⚖️ Bellman-Ford vs Dijkstra

Negative edges

Bellman-Ford handles them. Dijkstra assumes non-negative weights — a single negative edge can produce incorrect results.

Negative cycles

Bellman-Ford detects them explicitly. Dijkstra quietly loops forever or returns −∞.

Speed

Bellman-Ford is O(V·E) in the worst case. Dijkstra with a heap is O((V+E) log V) — faster when all weights are non-negative.

←Previous Algorithm
Depth-First Search
GraphO(V+E)
Next Algorithm→
Floyd-Warshall
O(V³)Graph

Click nodes to set source/target · Drag nodes to rearrange layout · Use controls to step through V−1 relaxation passes