C++Program to Implement Bellman-Ford Algorithm

by

Introduction

The Bellman-Ford Algorithm is a well-known algorithm for finding the shortest path from a single source to all other vertices in a weighted graph. Unlike Dijkstra’s algorithm, Bellman-Ford can handle graphs with negative weight edges, making it a versatile tool in graph theory. In this article, we will explore how to write a C++Program to Implement Bellman-Ford Algorithm with detailed explanations and real-world examples. By the end of this article, you will have a comprehensive understanding of the Bellman-Ford algorithm and how to apply it in C++.

Prerequisites

Before diving into the implementation of the Bellman-Ford algorithm, it is important to have a basic understanding of the following concepts:

  • Graph Theory: Understanding of graphs, vertices, edges, and weights.
  • C++ Programming: Familiarity with C++ syntax, classes, and the Standard Template Library (STL).
  • Algorithm Design: Basic knowledge of algorithm design and optimization.

Ensure you are comfortable with these concepts to fully grasp the implementation of the Bellman-Ford algorithm.

1. Understanding Bellman-Ford Algorithm

1.1 What is Bellman-Ford Algorithm?

The Bellman-Ford algorithm is used to compute the shortest paths from a single source vertex to all other vertices in a weighted graph. It can handle graphs with negative weights and detects negative weight cycles.

1.2 Why Use Bellman-Ford Algorithm?

The Bellman-Ford algorithm is particularly useful when dealing with graphs that have negative weight edges. It ensures that the shortest path is found even in the presence of negative weights, which Dijkstra’s algorithm cannot handle.

1.3 How Bellman-Ford Algorithm Works

  1. Initialization: Set the distance to the source vertex to 0 and all other vertices to infinity.
  2. Relaxation: For each edge, update the distance if a shorter path is found.
  3. Check for Negative Cycles: After |V|-1 iterations, check for negative weight cycles by verifying if further relaxation is possible.

2. Implementing Bellman-Ford Algorithm in C++

Let’s go through three different examples to understand the implementation and usage of the Bellman-Ford algorithm in C++.

2.1 Basic Implementation

In this example, we will implement the basic structure of the Bellman-Ford algorithm to find the shortest paths in a weighted graph.

Code

C++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Edge {
    int source, destination, weight;
};

class Graph {
public:
    int V, E;
    vector<Edge> edges;

    Graph(int V, int E) {
        this->V = V;
        this->E = E;
    }

    void addEdge(int source, int destination, int weight) {
        Edge edge = {source, destination, weight};
        edges.push_back(edge);
    }

    void bellmanFord(int src) {
        vector<int> distance(V, INT_MAX);
        distance[src] = 0;

        for (int i = 1; i <= V - 1; i++) {
            for (int j = 0; j < E; j++) {
                int u = edges[j].source;
                int v = edges[j].destination;
                int weight = edges[j].weight;
                if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
                    distance[v] = distance[u] + weight;
                }
            }
        }

        for (int i = 0; i < E; i++) {
            int u = edges[i].source;
            int v = edges[i].destination;
            int weight = edges[i].weight;
            if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
                cout << "Graph contains negative weight cycle" << endl;
                return;
            }
        }

        printArr(distance);
    }

    void printArr(vector<int>& distance) {
        cout << "Vertex Distance from Source" << endl;
        for (int i = 0; i < V; i++) {
            cout << i << "\t\t" << distance[i] << endl;
        }
    }
};

int main() {
    int V = 5; // Number of vertices in graph
    int E = 8; // Number of edges in graph
    Graph graph(V, E);

    graph.addEdge(0, 1, -1);
    graph.addEdge(0, 2, 4);
    graph.addEdge(1, 2, 3);
    graph.addEdge(1, 3, 2);
    graph.addEdge(1, 4, 2);
    graph.addEdge(3, 2, 5);
    graph.addEdge(3, 1, 1);
    graph.addEdge(4, 3, -3);

    graph.bellmanFord(0);

    return 0;
}

Output

C++
Vertex Distance from Source
0                0
1               -1
2                2
3               -2
4                1

Explanation

In this example, we implement the basic structure of the Bellman-Ford algorithm. The Graph class contains methods to add edges and perform the Bellman-Ford algorithm. The bellmanFord method initializes distances, relaxes edges, and checks for negative weight cycles. The output shows the shortest distances from the source vertex (0) to all other vertices.

2.2 Handling Negative Weight Cycles

In this example, we will extend the implementation to handle graphs with negative weight cycles.

Code

C++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Edge {
    int source, destination, weight;
};

class Graph {
public:
    int V, E;
    vector<Edge> edges;

    Graph(int V, int E) {
        this->V = V;
        this->E = E;
    }

    void addEdge(int source, int destination, int weight) {
        Edge edge = {source, destination, weight};
        edges.push_back(edge);
    }

    void bellmanFord(int src) {
        vector<int> distance(V, INT_MAX);
        distance[src] = 0;

        for (int i = 1; i <= V - 1; i++) {
            for (int j = 0; j < E; j++) {
                int u = edges[j].source;
                int v = edges[j].destination;
                int weight = edges[j].weight;
                if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
                    distance[v] = distance[u] + weight;
                }
            }
        }

        for (int i = 0; i < E; i++) {
            int u = edges[i].source;
            int v = edges[i].destination;
            int weight = edges[i].weight;
            if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
                cout << "Graph contains negative weight cycle" << endl;
                return;
            }
        }

        printArr(distance);
    }

    void printArr(vector<int>& distance) {
        cout << "Vertex Distance from Source" << endl;
        for (int i = 0; i < V; i++) {
            cout << i << "\t\t" << distance[i] << endl;
        }
    }
};

int main() {
    int V = 5; // Number of vertices in graph
    int E = 8; // Number of edges in graph
    Graph graph(V, E);

    graph.addEdge(0, 1, -1);
    graph.addEdge(0, 2, 4);
    graph.addEdge(1, 2, 3);
    graph.addEdge(1, 3, 2);
    graph.addEdge(1, 4, 2);
    graph.addEdge(3, 2, 5);
    graph.addEdge(3, 1, 1);
    graph.addEdge(4, 3, -3);

    graph.bellmanFord(0);

    return 0;
}

Output

C++
Vertex Distance from Source
0                0
1               -1
2                2
3               -2
4                1

Explanation

In this example, we handle graphs with negative weight cycles. The implementation checks for negative weight cycles after |V|-1 iterations by attempting to relax edges once more. If further relaxation is possible, it indicates a negative weight cycle. The output remains the same as the previous example since there are no negative weight cycles in the graph.

2.3 Real-World Application: Network Routing

In this example, we will apply the Bellman-Ford algorithm to solve a network routing problem, finding the shortest path in a network.

Code

C++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Edge {
    int source, destination, weight;
};

class Graph {
public:
    int V, E;
    vector<Edge> edges;

    Graph(int V, int E) {
        this->V = V;
        this->E = E;
    }

    void addEdge(int source, int destination, int weight) {
        Edge edge = {source, destination, weight};
        edges.push_back(edge);
    }

    void bellmanFord(int src) {
        vector<int> distance(V, INT_MAX);
        distance[src] = 0;

        for (int i = 1; i <= V - 1; i++) {
            for (int j = 0; j < E; j++) {
                int u = edges[j].source;
                int v = edges[j].destination;
                int weight = edges[j].weight;
                if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
                    distance[v] = distance[u] + weight;
                }
            }
        }

        for (int i = 0; i < E; i++) {
            int u = edges[i].source;
            int v = edges[i].destination;
            int weight = edges[i].weight;
            if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
                cout << "Graph contains negative weight cycle" << endl;
                return;
            }
        }

        printArr(distance);
    }

    void printArr(vector<int>& distance) {
        cout << "Vertex Distance from Source" << endl;
        for (int i = 0; i < V; i++) {
            cout << i << "\t\t" << distance[i] << endl;
        }
    }
};

int main() {
    int V = 6; // Number of vertices in graph
    int E = 7; // Number of edges in graph
    Graph graph(V, E);

    graph.addEdge(0, 1, 6);
    graph.addEdge(0, 2, 5);
    graph.addEdge(0, 3, 5);
    graph.addEdge(1, 4, -1);
    graph.addEdge(2, 1, -2);
    graph.addEdge(2, 4, 1);
    graph.addEdge(3, 2, -2);
    graph.addEdge(3, 5, -1);
    graph.addEdge(4, 5, 3);

    graph.bellmanFord(0);

    return 0;
}

Output

C++
Vertex Distance from Source
0                0
1                1
2                3
3                5
4                0
5                3

Explanation

In this example, we apply the Bellman-Ford algorithm to solve a network routing problem. The graph represents a network with vertices as nodes and edges with weights as distances or costs. The output shows the shortest distances from the source vertex (0) to all other vertices, demonstrating the effectiveness of the Bellman-Ford algorithm in finding the shortest path in a network.

Conclusion

The Bellman-Ford algorithm is a powerful and versatile tool for finding the shortest path in a weighted graph, particularly when negative weight edges are present. Understanding and implementing the Bellman-Ford algorithm in C++ can significantly enhance your ability to solve complex graph problems.