Bellman-Ford Algorithm Visualization

How it works:

The Bellman-Ford algorithm can handle negative edge weights and detect negative cycles. It works by:

  1. Initializing distances (source = 0, others = ∞)
  2. Relaxing all edges |V| - 1 times
  3. Checking for negative cycles with an additional iteration

Edge Selection Order: In each iteration, all edges are processed in the order they are defined.

Comparison with Dijkstra: While Dijkstra's algorithm cannot handle negative weights, Bellman-Ford can.

SPFA Optimization: The Shortest Path Faster Algorithm (SPFA) is an optimization of Bellman-Ford. It uses a queue to process only the nodes whose distances have been updated, potentially reducing the number of relaxations needed. This optimization often leads to faster convergence in practice, even though the worst-case time complexity remains O(VE).

Explanation

Algorithm initialized. Starting from source node S.

Current Edge
Relaxed Edge
Negative Cycle