Bellman–Ford Algorithm | DSA in C++ - Software Development PDF Download

Introduction

The Bellman-Ford algorithm is a popular algorithm used in graph theory to find the shortest path between two vertices in a graph. It is particularly useful in scenarios where the graph contains negative-weight edges, unlike other popular algorithms like Dijkstra's algorithm. In this article, we will explore the Bellman-Ford algorithm, its implementation in C++, and provide multiple examples and sample problems to solidify our understanding.

What is the Bellman-Ford Algorithm?

The Bellman-Ford algorithm is a single-source shortest path algorithm that computes the shortest path from a source vertex to all other vertices in a weighted directed graph. It can handle graphs with negative-weight edges, making it more versatile than other algorithms like Dijkstra's algorithm.

Algorithm Steps

The Bellman-Ford algorithm operates by iteratively relaxing the edges of the graph. The basic steps of the algorithm are as follows:

• Initialize the distances from the source vertex to all other vertices as infinity, except for the source vertex itself, which is set to 0.
• Repeat the following step |V| - 1 times, where |V| is the number of vertices in the graph:
  • For each edge (u, v) with weight w, if the distance to vertex v can be improved by taking edge (u, v), update the distance to v as the minimum of its current distance and the distance to u plus w.
• After the iterations, check for negative-weight cycles by performing one more iteration. If any distance can be further improved, it means the graph contains a negative-weight cycle.

Implementing Bellman-Ford in C++

Here's an implementation of the Bellman-Ford algorithm in C++:

#include <iostream>

#include <vector>

struct Edge {

    int source;

    int destination;

    int weight;

};

void BellmanFord(std::vector<Edge>& edges, int numVertices, int source) {

    std::vector<int> distances(numVertices, INT_MAX);

    distances[source] = 0;

    for (int i = 1; i < numVertices; ++i) {

        for (const auto& edge : edges) {

            int u = edge.source;

            int v = edge.destination;

            int w = edge.weight;

            if (distances[u] != INT_MAX && distances[u] + w < distances[v]) {

                distances[v] = distances[u] + w;

            }

        }

    }

    // Check for negative-weight cycles

    for (const auto& edge : edges) {

        int u = edge.source;

        int v = edge.destination;

        int w = edge.weight;

        if (distances[u] != INT_MAX && distances[u] + w < distances[v]) {

            std::cout << "Graph contains a negative-weight cycle." << std::endl;

            return;

        }

    }

    // Print the shortest distances

    std::cout << "Shortest distances from source " << source << ":" << std::endl;

    for (int i = 0; i < numVertices; ++i) {

        std::cout << "Vertex " << i << ": " << distances[i] << std::endl;

    }

}

int main() {

    // Example usage

    std::vector<Edge> edges = {{0, 1, 4}, {0, 2, 5}, {1, 2, -2}, {1, 3, 4},

                               {1, 4, 3}, {2, 1, 1}, {2, 4, 2}, {3, 4, 4},

                               {4, 3, 1}};

    int numVertices = 5;

    int source = 0;

    BellmanFord(edges, numVertices, source);

    return 0;

}

Example 1: Finding the Shortest Path in a Graph

Consider the following graph:

     4       2

0 ------► 1 ------► 3

|         |         ▲

|        -2         |

|         |         |

▼         ▼         |

2 ------► 4 ◄------ 2

Let's use the Bellman-Ford algorithm to find the shortest path from vertex 0 (source) to all other vertices.

Output:

Shortest distances from source 0:

Vertex 0: 0

Vertex 1: 2

Vertex 2: 3

Vertex 3: 6

Vertex 4: 4

Explanation:

The algorithm finds the shortest distances from the source vertex (0) to all other vertices. For example, the shortest distance from vertex 0 to vertex 3 is 6. The algorithm iteratively relaxes the edges and updates the distances until no further improvements can be made.

Example 2: Detecting Negative Cycles

Consider the following graph:

     4       2

0 ------► 1 ------► 3

|         ▲         ▲

|        -2         |

|         |         |

▼         ▼         |

2 ◄------ 4 ◄------ 2

In this graph, there is a negative-weight cycle present.

Output:

Graph contains a negative-weight cycle.

Explanation:

The algorithm detects the presence of a negative-weight cycle during the additional iteration. A negative-weight cycle is a cycle whose total weight is negative. In this case, the cycle is (1 → 2 → 4 → 1) with a total weight of -1.

Sample Problems

Here are a few sample problems to practice the Bellman-Ford algorithm:

Problem 1: Consider the following graph. Use the Bellman-Ford algorithm to find the shortest path from vertex 0 to all other vertices.

     2       1

0 ------► 1 ------► 2

|         ▲         ▲

|        -1         |

|         |         |

▼         ▼         |

3 ------► 4 ◄------ 3

Problem 2:

Given a graph with n vertices and m edges, write a C++ program to detect if the graph contains any negative-weight cycles using the Bellman-Ford algorithm.

Conclusion

The Bellman-Ford algorithm is a valuable tool in graph theory for finding the shortest path in a graph, even in the presence of negative-weight edges. It allows us to solve a wide range of problems efficiently. By understanding the algorithm and studying the examples provided in this article, you should now have a good grasp of how to implement and use the Bellman-Ford algorithm in your own programs.