Bellman-Ford Shortest Path Analyzer

Visualize shortest path algorithm with negative cycle detection

1. Algorithm Manual
2. Build Network
3. Algorithm Parameters
4. Visualization

Bellman-Ford Algorithm Manual

Learn about the algorithm before using the tool. The Bellman-Ford algorithm finds shortest paths from a single source in weighted graphs, even with negative weights, and detects negative cycles.

Algorithm Steps

  1. Initialization: Set distance to source as 0 and all other distances as ∞ (INF).
  2. Relaxation: For V-1 iterations, relax all edges. For each edge (u, v) with weight w, if D[u] + w < D[v], update D[v] = D[u] + w and set P[v] = u.
  3. Negative Cycle Check: Perform one more iteration (Vth iteration). If any distance can be improved, a negative cycle exists.

Pseudocode

function BellmanFord(graph, source):
    // Step 1: Initialize distances and predecessors
    for each vertex v in graph:
        D[v] = INF
        P[v] = null
    D[source] = 0
    
    // Step 2: Relax edges repeatedly
    for i from 1 to V-1:
        for each edge (u, v) with weight w in graph:
            if D[u] != INF and D[u] + w < D[v]:
                D[v] = D[u] + w
                P[v] = u
    
    // Step 3: Check for negative-weight cycles
    for each edge (u, v) with weight w in graph:
        if D[u] != INF and D[u] + w < D[v]:
            return "Graph contains negative cycle"
    
    return D, P

Key Features

  • Handles graphs with negative edge weights
  • Detects negative cycles reachable from source
  • Guaranteed to find shortest paths in absence of negative cycles
  • Time complexity: O(V×E)

Applications

  • Routing protocols in computer networks
  • Currency arbitrage detection
  • Finding shortest paths with negative weights
  • Network flow problems

Ready to Start?

Click the button below to begin building your graph and running the Bellman-Ford algorithm.