Bellman-Ford Algorithm

# CHAPTER 27

Shortest Path Algorithms (Bellman-Ford) #

1. Introduction #

2. Learning Objectives #

• Explain why Bellman-Ford abandons Priority Queues.

• Trace the systematic execution of exactly $V - 1$ Relaxation passes.

• Identify and understand the threat of a "Negative Weight Cycle."

• Analyze the $O(V \times E)$ Time Complexity tradeoff.

3. The Execution Logic #

The Mechanics:

1. 1. Initialize: Create a Distance array initialized to Infinity, with the Start Node set to 0.

1. 2. The Massive Loop: Execute a massive overarching loop exactly $V - 1$ times (where $V$ is the number of Vertices).

1. 3. The Inner Iteration: Inside the massive loop, iterate through *every single Edge* in the entire graph.

1. 4. Relaxation: For every Edge, perform the standard evaluation: If (Dist[Source] + EdgeWeight < Dist[Destination]), overwrite it!

4. Why V - 1 Times? #

5. The Real Danger: Negative Weight Cycles #

The Radar Detection: Bellman-Ford runs its normal $V - 1$ passes to finalize the distances. Then, it maliciously runs one final extra pass. If any distances *still* shrink on the extra pass, it mathematically proves a massive Infinite Negative Cycle is ripping the graph apart! The algorithm instantly throws an error and aborts.

6. Implementation in Code #

// Java Example: Bellman-Ford Algorithm
class Edge {
    int source, dest, weight;
    Edge() { source = dest = weight = 0; }
}

public class BellmanFord {

    public void calculatePath(int V, int E, Edge[] edges, int start) {
        // 1. Initialize Distance Array
        int[] dist = new int[V];
        for (int i = 0; i < V; ++i) dist[i] = Integer.MAX_VALUE;
        dist[start] = 0;

        // 2. The Core Execution: Loop exactly V - 1 times
        for (int i = 1; i < V; ++i) {
            
            // 3. Blindly evaluate EVERY SINGLE EDGE sequentially
            for (int j = 0; j < E; ++j) {
                int u = edges[j].source;
                int v = edges[j].dest;
                int weight = edges[j].weight;

                // RELAXATION LOGIC
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }

        // 4. THE RADAR DETECTOR: Run one final extra pass!
        for (int j = 0; j < E; ++j) {
            int u = edges[j].source;
            int v = edges[j].dest;
            int weight = edges[j].weight;
            
            // If the math is STILL shrinking...
            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                System.out.println("CATASTROPHIC FAILURE: Graph contains a Negative Weight Cycle!");
                return; // Abort the universe!
            }
        }
    }
}

7. Complexity Analysis: The Price of Safety #

8. Real-World Applications #

1. 1. Financial Arbitrage (High-Frequency Trading): Wall Street servers map global currencies (USD, EUR, YEN) as Vertices and conversion rates as Negative Edges. By deploying Bellman-Ford to rapidly discover Negative Weight Cycles, the AI mathematically identifies "Arbitrage Loops"—converting currencies in a circle to print infinite free money before the market corrects itself!

1. 2. RIP Protocol: Older internet routers utilize localized variations of Bellman-Ford to broadcast dynamic routing updates safely.

9. Common Mistakes #

• Applying to Undirected Graphs with Negative Edges: If you have an Undirected Graph (two-way street) and an edge has a negative weight (e.g., -5), it inherently acts as a catastrophic Negative Cycle! You can just bounce back and forth across the edge forever (A->B->A->B), instantly causing the algorithm to crash. Bellman-Ford's magic is explicitly designed for Directed Graphs.

10. Exercises #

1. 1. If a Directed Graph has 10 Vertices and 15 Edges, exactly how many total edge-evaluations will the core loop execute?

1. 2. Why is Dijkstra mathematically incapable of detecting Negative Weight Cycles?

11. MCQs with Answers #

12. Interview Preparation #

• *Algorithmic Decision Making:* "You have a massive unweighted Graph. You need the shortest path. Do you use Dijkstra, Bellman-Ford, or Breadth-First Search (BFS)?" *(Answer: BFS! Dijkstra is $O(E \log V)$ overhead. Bellman-Ford is $O(V \times E)$ disaster. BFS inherently finds the shortest path on Unweighted graphs in blazing fast $O(V + E)$ Linear time! Never use heavy weighted algorithms on unweighted geometry!)*

13. Summary #

14. Next Chapter Recommendation #