Bellman-Ford Algorithm in C++

The Bellman-Ford Algorithm is a dynamic programming algorithm used to find the shortest path from a single source to all other vertices in a weighted graph. Unlike Dijkstra’s Algorithm, it can handle negative weight edges and can also detect negative weight cycles.

1. How Bellman-Ford Algorithm Works

• Step 1: Initialize distances from the source node to all other nodes as infinity (∞), except for the source itself, which is set to 0.
• Step 2: Repeat (V - 1) times (where V is the number of vertices):
  • For each edge (u, v, w), update the distance to v if a shorter path via u is found (dist[v] = min(dist[v], dist[u] + w)).
• Step 3: Perform one more iteration to check for negative weight cycles:
  • If any distance is updated in this step, a negative cycle exists.

2. C++ Implementation of Bellman-Ford Algorithm

Here’s the complete C++ implementation using an edge list representation.

Code Example

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// Structure to represent an edge
struct Edge {
    int src, dest, weight;
};

// Bellman-Ford Algorithm Function
void bellmanFord(int V, int E, vector<Edge>& edges, int src) {
    // Distance array initialized to "infinity"
    vector<int> dist(V, INT_MAX);
    
    // Set the source distance to 0
    dist[src] = 0;

    // Step 1: Relax all edges V-1 times
    for (int i = 0; i < V - 1; i++) {
        for (const auto& edge : edges) {
            if (dist[edge.src] != INT_MAX && dist[edge.src] + edge.weight < dist[edge.dest]) {
                dist[edge.dest] = dist[edge.src] + edge.weight;
            }
        }
    }

    // Step 2: Check for negative weight cycles
    for (const auto& edge : edges) {
        if (dist[edge.src] != INT_MAX && dist[edge.src] + edge.weight < dist[edge.dest]) {
            cout << "Graph contains a negative weight cycle!\n";
            return;
        }
    }

    // Output shortest distances
    cout << "Shortest distances from source node " << src << ":\n";
    for (int i = 0; i < V; i++) {
        cout << "Node " << i << " : " << (dist[i] == INT_MAX ? "INF" : to_string(dist[i])) << endl;
    }
}

int main() {
    int V = 5; // Number of vertices
    int E = 7; // 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}
    };

    int source = 0; // Start node
    bellmanFord(V, E, edges, source);

    return 0;
}

3. Code Explanation

Step-by-Step Breakdown

1. Graph Representation:
   • We use an edge list, where each edge is stored as {source, destination, weight}.
   • This makes it efficient for sparse graphs (where edges are much fewer than V²).
2. Distance Initialization:
   • We initialize all distances as INT_MAX (infinity).
   • The source node’s distance is set to 0.
3. Relaxation of Edges (V-1 times):
   • Each edge (u, v, w) is checked, and if a shorter path is found (dist[u] + w < dist[v]), we update dist[v].
   • This guarantees the shortest path because a shortest path in a graph can have at most V-1 edges.
4. Detecting Negative Weight Cycles:
   • If any edge (u, v, w) can still be relaxed, it means a negative cycle exists.
5. Final Output:
   • The shortest distances from the source node to all other nodes are displayed.

4. Time Complexity Analysis

• Best case: If the graph is sparse (E ≈ V), it runs in O(V²), which is slower than Dijkstra (O((V+E) log V)).
• Worst case: If the graph is dense (E ≈ V²), it runs in O(V³), making it inefficient for large graphs.

5. Example Output

For the given graph, running the program produces:

Shortest distances from source node 0:
Node 0 : 0
Node 1 : -1
Node 2 : 2
Node 3 : -2
Node 4 : 1

Explanation:

• 0 → 1 (-1), 0 → 2 (4), 1 → 2 (3), 1 → 3 (2), 1 → 4 (2), etc.
• The negative weight edge 4 → 3 (-3) makes dist[3] smaller than expected.