Shortest Path

Bellman-Ford Algorithm

Shortest path algorithm capable of handling negative edge weights and detecting negative cycles.

What is Bellman-Ford Algorithm?

The Bellman-Ford algorithm computes shortest paths from a single source vertex to all other vertices in a weighted graph. Unlike Dijkstra's algorithm, it supports negative edge weights. It works by repeatedly relaxing all edges V-1 times. On the V-th iteration, it checks for negative-weight cycles; if a path's cost decreases, a negative cycle exists, making a finite shortest path impossible.

Key Characteristics:

  • Supports negative edge weights.
  • Detects negative-weight cycles.
  • Dynamic programming approach via bottom-up relaxation.
  • Slower than Dijkstra but more versatile.

Complexity Analysis

Avg Time Complexity: O(V * E) where V is vertices count and E is edge count
Space Complexity: O(V) distance storage table
Best Case: O(E) (all shortest paths found in first iteration)
Worst Case: O(V * E) (all iterations relaxed exhaustively)

How it Works Step-by-Step

  1. Initialize: Set distance to source node to 0, and all other nodes to infinity.
  2. Relax Edges: Loop V-1 times. In each iteration, for every edge (u, v) with weight w, if dist[u] + w < dist[v], set dist[v] = dist[u] + w.
  3. Cycle Check: Loop through all edges one more time. If dist[u] + w < dist[v] for any edge, report that a negative cycle exists.

Code Implementation

Worked Trace Example

Graph with A->B (4), B->C (-2), A->C (5). Source A:
1. Initial: dist[A]=0, dist[B]=∞, dist[C]=∞.
2. Iteration 1: Relax A->B: dist[B]=4. Relax B->C: dist[C]=4-2=2. Relax A->C: dist[C]=min(2,5)=2.
3. Iteration 2: No changes. dist[A]=0, dist[B]=4, dist[C]=2.
Result: Optimal paths found.

Ready to Understand Bellman-Ford Algorithm Visually?

Don't just read about it. Launch our interactive, premium algorithm visualizer to step through calculations in real-time.

Launch Bellman-Ford Algorithm Visualizer →