Bellman-Ford Algorithm

Shortestpath: Bellman-Ford Algorithm

In our previous tutorial, we explored Dijkstra's Algorithm and celebrated its blazing O(E log V) efficiency for finding the shortest path.

However, Dijkstra makes a critical, greedy assumption: adding an edge to a path will always make the total distance greater or equal. If an edge can somehow subtract from the distance (a negative weight), Dijkstra will blindly freeze nodes prematurely and return incorrect paths. To solve this, we must use the Bellman-Ford Algorithm.

1. The Threat of Negative Edge Weights

Do negative weights actually exist in the real world? Absolutely!

• Finance & Trading: Vertices are currencies, and edges are exchange rates. A negative edge might represent a profit or an arbitrage opportunity.
• Chemistry/Thermodynamics: Edges represent energy absorption (positive) or energy release (negative).
• Logistics: Driving down a road costs fuel (positive), but picking up a payload along the way grants a financial bonus (negative).

Dijkstra would assume S → A (Cost 4) is the best path. Bellman-Ford correctly identifies that taking the longer detour S → B → A actually lowers the final cost to 3.

2. How Bellman-Ford Works

Unlike Dijkstra, which uses a delicate Priority Queue to greedily pick the closest node, Bellman-Ford uses a pure Dynamic Programming (Brute Force) approach.

Instead of guessing which node to check, Bellman-Ford says: "I am simply going to relax EVERY single edge in the entire graph, over and over again, until no more improvements can possibly be made."

The Logic

1. Initialize: Set the distance to the starting node to 0, and all other nodes to Infinity.
2. Relax Everything: Loop through every single edge in the entire graph. If the distance to the starting node plus the edge's weight is cheaper than the target node's currently known distance, update it!
3. Repeat: Do Step 2 exactly V - 1 times (where V is the total number of Vertices).

Why exactly V - 1 times? Because the absolute longest possible path between any two nodes in a graph (without running into a loop) will contain at most V - 1 edges. By relaxing everything V - 1 times, we guarantee that the correct distances have fully propagated throughout the entire network!

3. The Fatal Scenario: Negative Cycles

There is one thing that even Bellman-Ford cannot mathematically solve: A Negative Weight Cycle.

Imagine a loop between two nodes: Node X to Node Y costs 2, but Node Y back to Node X costs -5. Every time you run in this circle, your total cost drops by -3. You could loop infinitely to reach a score of -1,000,000. The concept of a "Shortest Path" ceases to exist!

Bellman-Ford is brilliant because it can detect if this is happening.

The Detection Trick

After running the standard loop V - 1 times, we know the graph should be perfectly solved. So, we run the loop one more time. If any distance miraculously updates and gets cheaper on this V-th iteration, it mathematically proves a Negative Cycle exists, and we can immediately abort the program and throw an error!

4. Implementing Bellman-Ford in Python

Because we don't need a Priority Queue, implementing Bellman-Ford is actually significantly simpler to code than Dijkstra. We just need standard arrays and loops.

def bellman_ford(vertices, edges, start):
    # 1. Initialize distances to Infinity
    distances = {v: float('inf') for v in vertices}
    distances[start] = 0
    previous_nodes = {v: None for v in vertices}
    # 2. Relax all edges (V - 1) times
    for _ in range(len(vertices) - 1):
        for u, v, weight in edges:
            # If path via 'u' is cheaper, update 'v'
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight
                previous_nodes[v] = u
    # 3. Run one final time to check for Negative Cycles
    for u, v, weight in edges:
        if distances[u] != float('inf') and distances[u] + weight < distances[v]:
            print("Error: Graph contains a Negative Weight Cycle!")
            return None, None
    return distances, previous_nodes
# Graph from the SVG Diagram
vertices = ['S', 'A', 'B', 'C']
edges = [
    ('S', 'A', 4),
    ('S', 'B', 5),
    ('B', 'A', -2),  # The Negative Edge
    ('A', 'C', 3),
    ('B', 'C', 4)
]

distances, previous = bellman_ford(vertices, edges, 'S')
if distances:
    print("Minimum Distances:", distances)

5. Implementing Bellman-Ford in JavaScript

Here is the same algorithmic logic implemented in modern JavaScript. Notice how we represent our edges as an array of structured arrays [start_node, end_node, weight].

function bellmanFord(vertices, edges, start) {
  const distances = {};
  const previous = {};
  
  // 1. Initialize
  vertices.forEach(v => {
    distances[v] = Infinity;
    previous[v] = null;
  });
  distances[start] = 0;
  // 2. Relax all edges V-1 times
  for (let i = 0; i < vertices.length - 1; i++) {
    for (let [u, v, weight] of edges) {
      if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
        distances[v] = distances[u] + weight;
        previous[v] = u;
      }
    }
  }
  // 3. Detect Negative Cycles
  for (let [u, v, weight] of edges) {
    if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
      console.error("Negative weight cycle detected!");
      return null;
    }
  }
  return distances;
}
const vList = ['S', 'A', 'B', 'C'];
const eList = [
  ['S', 'A', 4],
  ['S', 'B', 5],
  ['B', 'A', -2],
  ['A', 'C', 3],
  ['B', 'C', 4]
];
const result = bellmanFord(vList, eList, 'S');
console.log("Final Distances:", result);
// Display output directly in the editor's web preview
if (typeof document !== 'undefined') {
  document.body.innerHTML = &lt;h3&gt;Shortest Paths from S:&lt;/h3&gt;&lt;pre&gt;${JSON.stringify(result, null, 2)}&lt;/pre&gt;;
}

6. Algorithmic Complexity

Because Bellman-Ford forcibly loops over all edges over and over, it is heavily punished when it comes to raw speed compared to Dijkstra.

• Time Complexity: O(V * E) where V is the number of Vertices and E is the number of Edges. In a highly dense graph where E approaches V², the time complexity degrades to a brutal O(V³).
• Space Complexity: O(V) to store the array of distances for each vertex.

Because of this slow speed, you should always use Dijkstra if you know your data is entirely positive. You only bring out Bellman-Ford as an emergency tool when negative edge weights are expected.