🔄 Bellman-Ford Algorithm – Shortest Path in Graphs

The **Bellman-Ford Algorithm** is a **graph algorithm** used for finding the **shortest path from a single source vertex to all other vertices** in a **weighted graph**. Unlike **Dijkstra's Algorithm**, Bellman-Ford can **handle graphs with negative weight edges**.

⚡ Key Features of Bellman-Ford Algorithm

  • ✅ Works for both **positive and negative** edge weights.
  • ✅ Detects **negative weight cycles** in the graph.
  • ✅ Solves **Single-Source Shortest Path** problems.
  • ❌ **Slower than Dijkstra's Algorithm** (O(V × E) time complexity).

⚙️ How Does the Bellman-Ford Algorithm Work?

The algorithm works by **iteratively relaxing all edges** in the graph (V - 1) times to guarantee the shortest distance to each vertex.

📌 Step-by-Step Process

  1. ✅ **Initialize** the distance to all vertices as **infinity (∞)**, except the source vertex (0).
  2. 🔄 **Relax all edges** V-1 times (where V = number of vertices).
  3. 🚨 **Check for Negative Weight Cycles** – If relaxation is still possible, a **negative cycle exists**.

🔢 Mathematical Formula for Edge Relaxation

The shortest path estimate is updated using:


                if (dist[u] + weight(u, v) < dist[v]):
                    dist[v] = dist[u] + weight(u, v)

🛠️ Bellman-Ford Algorithm Implementation (C++)


                #include <iostream>
                #include <vector>
                #include <limits.h>
            
                using namespace std;
            
                struct Edge {
                    int src, dest, weight;
                };
            
                void bellmanFord(vector<Edge> &edges, int V, int E, int source) {
                    vector<int> dist(V, INT_MAX);
                    dist[source] = 0;
            
                    for (int i = 1; i < V; i++) {
                        for (int j = 0; j < E; j++) {
                            int u = edges[j].src;
                            int v = edges[j].dest;
                            int weight = edges[j].weight;
                            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                                dist[v] = dist[u] + weight;
                            }
                        }
                    }
            
                    // Checking for Negative Weight Cycles
                    for (int j = 0; j < E; j++) {
                        int u = edges[j].src;
                        int v = edges[j].dest;
                        int weight = edges[j].weight;
                        if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                            cout << "Graph contains a negative weight cycle!";
                            return;
                        }
                    }
            
                    // Printing the shortest distances
                    cout << "Vertex Distance from Source:\n";
                    for (int i = 0; i < V; i++) {
                        cout << i << " \t\t " << dist[i] << endl;
                    }
                }
            
                int main() {
                    int V = 5; // Number of vertices
                    int E = 8; // Number of edges
                    vector<Edge> edges = {
                        {0, 1, -1}, {0, 2, 4}, {1, 2, 3}, {1, 3, 2},
                        {1, 4, 2}, {3, 2, 5}, {3, 1, 1}, {4, 3, -3}
                    };
            
                    bellmanFord(edges, V, E, 0);
                    return 0;
                }

🔄 Comparison: Bellman-Ford vs Dijkstra's Algorithm

Feature Bellman-Ford Dijkstra's Algorithm
Time Complexity O(V × E) O(V log V) (using Priority Queue)
Handles Negative Edges ✅ Yes ❌ No
Handles Negative Cycles ✅ Yes ❌ No
Performance Slower (Iterative) Faster (Greedy Approach)

⏳ Time Complexity Analysis

  • ✅ **Best Case**: O(V × E) – No negative weight cycle.
  • ❌ **Worst Case**: O(V × E) – Graph with dense edges.

🌍 Real-World Applications of Bellman-Ford Algorithm

  • 📡 **Routing Protocols** – Used in **distance vector routing algorithms**.
  • 📂 **Network Packet Transmission** – Optimizes network data flow.
  • 🚗 **Traffic Navigation Systems** – Finds **optimal shortest paths**.
  • 📊 **Financial Systems** – Detects arbitrage opportunities in stock trading.

🔗 Next Topics