Bellman-Ford Algorithm Visualization

Interactive shortest path algorithm with negative edge detection

GitHub Repo

Statistics

Current Iteration
0 / 0
Nodes
0
Edges
0
Execution Time
0.00 ms
Shortest Path Length
N/A
Negative Cycle
Not Detected

Graph Visualization

Source
Target
Regular
Processing

Path Selection

Controls

Algorithm Pseudocode

function BellmanFord(graph, source):
        // Step 1: Initialize distances from source
        for each vertex v in graph:
            distance[v] := INFINITY
            predecessor[v] := NULL
        distance[source] := 0

        // Step 2: Relax edges repeatedly |V|-1 times
        for i from 1 to |V| - 1:
            for each edge (u, v) with weight w in graph:
                if distance[u] + w < distance[v]:
                    distance[v] := distance[u] + w
                    predecessor[v] := u

        // Step 3: Check for negative-weight cycles
        for each edge (u, v) with weight w in graph:
            if distance[u] + w < distance[v]:
                return "Graph contains a negative-weight cycle"

        return distance, predecessor

Algorithm Steps

Run the algorithm to see the steps.

What is Bellman-Ford?

The Bellman-Ford algorithm is a single-source shortest path algorithm that computes the shortest paths from a single source vertex to all other vertices in a weighted directed graph.

Key Characteristics:

  • Can handle graphs with negative edge weights
  • Detects the presence of negative cycles
  • Works with both directed and undirected graphs
  • More versatile than Dijkstra's algorithm for certain scenarios

Historical Context:

Named after Richard Bellman and Lester Ford Jr., this algorithm was developed in the 1950s and 1960s. It's particularly important in network routing and distributed systems where negative weights can represent costs, delays, or other metrics that need to be minimized.

How it Works

Algorithm Steps:

1
Initialization: Set distance to source vertex as 0 and all other vertices as infinity (∞)
2
Relaxation: For V-1 iterations (where V = number of vertices), relax all edges. For each edge (u,v) with weight w, if distance[u] + w < distance[v], update distance[v]
3
Negative Cycle Detection: Run one more iteration. If any distance can still be reduced, a negative cycle exists
4
Result: If no negative cycle exists, the distances array contains the shortest path lengths from source to all vertices

Why V-1 iterations?

In the worst case, the shortest path between any two vertices can have at most V-1 edges (since we can't repeat vertices without creating a cycle). Therefore, V-1 relaxations are sufficient to find all shortest paths.

Use Cases & Benefits

Use Cases:

  • Currency exchange systems and arbitrage detection
  • Network routing protocols (distance-vector)
  • Game theory and competitive analysis
  • Financial modeling with debt/credit systems
  • Social network analysis with negative relationships

Benefits:

  • Handles negative edge weights correctly
  • Detects negative cycles in the graph
  • Simple and straightforward implementation
  • Works with directed graphs
  • Guaranteed to find shortest paths if no negative cycles exist

Drawbacks & Complexity

Drawbacks:

  • Slower than Dijkstra's algorithm for positive weights
  • Cannot find shortest paths when negative cycles exist
  • Less efficient for dense graphs
  • Requires V-1 iterations regardless of early termination
  • Not suitable for real-time applications due to complexity

Complexity Analysis:

Time Complexity: O(V × E)
Space Complexity: O(V)
Where V = number of vertices, E = number of edges