Bellman-Ford Algorithm Visualizer

Visualize how the Bellman-Ford algorithm finds shortest paths even with negative edge weights. Build a weighted graph and watch it relax edges iteratively.

Visualize Bellman-Ford

How It Works

The Bellman-Ford algorithm finds the shortest paths from a single source node to all other nodes in a weighted graph. Unlike Dijkstra's, it handles negative edge weights and can detect negative-weight cycles. It was developed by Richard Bellman and Lester Ford Jr. in 1958.

The algorithm works by repeatedly relaxing all edges in the graph. After V-1 iterations (where V is the number of vertices), all shortest paths are guaranteed to be found. A final iteration checks for negative-weight cycles.

  1. 1

    Initialize the source node distance to 0 and all others to infinity

  2. 2

    Repeat V-1 times: for each edge, check if the path through this edge is shorter

  3. 3

    If a shorter path is found, update the distance (relax the edge)

  4. 4

    After V-1 iterations, all shortest paths are finalized

  5. 5

    Run one more iteration over all edges to check for negative-weight cycles

  6. 6

    If any distance can still be reduced, a negative-weight cycle exists

Key Properties

Time Complexity

O(V × E) where V is the number of vertices and E is the number of edges.

Negative Weights

Handles graphs with negative edge weights, unlike Dijkstra's which requires non-negative weights.

Cycle Detection

Detects negative-weight cycles that would make shortest paths undefined (infinitely negative).

Edge Relaxation

Iteratively relaxes all edges, progressively improving distance estimates until they converge.

Common Use Cases

  • Currency arbitrage — detecting profitable exchange rate cycles in financial networks
  • Distance-vector routing — protocols like RIP use Bellman-Ford for distributed routing
  • Constraint systems — solving systems of difference constraints in scheduling

Frequently Asked Questions

What is the Bellman-Ford algorithm?
The Bellman-Ford algorithm finds the shortest paths from a single source to all other vertices in a weighted graph. Unlike Dijkstra's, it correctly handles negative edge weights and can detect negative-weight cycles.
Why does Bellman-Ford run V-1 iterations?
In a graph with V vertices, the shortest path between any two nodes can have at most V-1 edges. Each iteration guarantees at least one more edge of each shortest path is finalized, so V-1 iterations are sufficient to find all shortest paths.
What is a negative-weight cycle?
A negative-weight cycle is a cycle in a graph where the sum of edge weights is negative. If such a cycle is reachable from the source, shortest paths are undefined because you can keep traversing the cycle to reduce the distance infinitely.
When should I use Bellman-Ford over Dijkstra's?
Use Bellman-Ford when the graph has negative edge weights, which Dijkstra's cannot handle. If all weights are non-negative, Dijkstra's is faster with O((V + E) log V) time compared to Bellman-Ford's O(V × E).

Ready to see it in action?

Open the Visualizer