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

Introduction

The Bellman-Ford algorithm is a fundamental graph traversal algorithm used to find the shortest path between a source vertex and all other vertices in a weighted directed graph. It is particularly useful in scenarios where negative edge weights are present. In this article, we will explore the Bellman-Ford algorithm in the context of data structures and algorithms using C++. We'll cover the basic concepts, provide simple code examples with explanations, and conclude with some sample problems and their solutions.

What is the Bellman-Ford Algorithm?

Algorithm Steps

The steps involved in the Bellman-Ford algorithm are as follows:

• Initialize all distances to infinity and the distance of the source vertex to 0.
• Relax all edges repeatedly (V-1) times, where V is the number of vertices.
• Check for negative cycles. If any distance can be further minimized, a negative cycle exists.

Implementation in C++

Let's take a look at a basic implementation of the Bellman-Ford algorithm in C++:

#include <iostream>

#include <vector>

struct Edge {

    int source;

    int destination;

    int weight;

};

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

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

    distance[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 (distance[u] != INT_MAX && distance[u] + w < distance[v])

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

        }

    }

    for (const auto& edge : edges) {

        int u = edge.source;

        int v = edge.destination;

        int w = edge.weight;

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

            std::cout << "Negative cycle detected!\n";

            return;

        }

    }

    // Print shortest distances

    std::cout << "Vertex\tDistance from Source\n";

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

        std::cout << i << "\t" << distance[i] << "\n";

}

int main() {

    // Define the graph

    std::vector<Edge> edges = {

        {0, 1, 4},

        {0, 2, 1},

        {1, 3, 1},

        {2, 1, 2},

        {2, 3, 5},

        {3, 4, 3}

    };

    int numVertices = 5;

    int source = 0;

    bellmanFord(edges, numVertices, source);

    return 0;

}

Example 1: Finding Shortest Paths

Consider the graph given in the code example. We will find the shortest paths from the source vertex 0 to all other vertices using the Bellman-Ford algorithm.

Output:

Vertex  Distance from Source

0       0

1       3

2       1

3       4

4       7

Explanation:

The algorithm computes the shortest distances from the source vertex to all other vertices. The output shows the vertex number and its corresponding distance from the source.

Example 2: Detecting Negative Cycles

Now, let's modify the graph to introduce a negative cycle. We will add an edge with a negative weight from vertex 3 to vertex 1 and run the Bellman-Ford algorithm again.
Modified graph:

std::vector<Edge> edges = {

    {0, 1, 4},

    {0, 2, 1},

    {1, 3, 1},

    {2, 1, 2},

    {2, 3, 5},

    {3, 4, 3},

    {3, 1, -6}  // Negative weight edge

};

Output:

Negative cycle detected!

Explanation:

The algorithm detects the presence of a negative cycle since the distance from vertex 3 to vertex 1 can be further minimized by taking the negative cycle repeatedly.

Sample Problems

Let's explore a couple of sample problems to solidify our understanding.
Problem 1: Given a graph with the following edges and weights, find the shortest paths from vertex 0 to all other vertices using the Bellman-Ford algorithm.
Graph:

     2

(0)---->(1)

  |     /\

  | 3 /  \ -1

  |  /    \

  ∨ /      ∨

(2)---->(3)

    -4

Solution:

Running the Bellman-Ford algorithm on this graph will yield the following output:

Vertex  Distance from Source

0       0

1       2

2       3

3      -1

Problem 2: Given a graph with the following edges and weights, determine if there is a negative cycle using the Bellman-Ford algorithm.
Graph:

   1

(0)-->(1)

 ^    /\

 |  4/  \3

 |  /    \

 | ∨      ∨

(3)<--(2)

    -2

Solution:

Running the Bellman-Ford algorithm on this graph will detect a negative cycle between vertices 1, 2, and 3.

Output:

Negative cycle detected!

Conclusion

The Bellman-Ford algorithm is a powerful tool for finding the shortest path in a graph, even when negative edge weights are present. It ensures correctness by detecting negative cycles and terminates successfully if no negative cycles are found. Understanding this algorithm is crucial for solving various graph traversal problems efficiently.