Detect a negative cycle in a Graph | (Bellman Ford) | DSA in C++ - Software Development PDF Download

Introduction

In graph theory, a negative cycle is a cycle in a directed graph where the sum of the weights of the edges in the cycle is negative. Detecting negative cycles is an important problem in various applications such as detecting arbitrage opportunities in financial markets or identifying negative feedback loops in systems. The Bellman-Ford algorithm is a popular algorithm that can be used to detect negative cycles in a graph efficiently. In this article, we will explore the Bellman-Ford algorithm and its implementation in C++.

What is the Bellman-Ford algorithm?

The Bellman-Ford algorithm is a single-source shortest path algorithm that can handle graphs with negative edge weights. It not only finds the shortest paths from a source vertex to all other vertices but also detects the presence of negative cycles in the graph.

How does the Bellman-Ford algorithm work?

The Bellman-Ford algorithm works by iteratively relaxing the edges in the graph. The relaxation process updates the distance values of vertices by considering the edges one by one. It repeatedly relaxes all the edges until no further improvement can be made. If after the completion of all iterations, a vertex's distance can still be relaxed, it means that there exists a negative cycle in the graph.

Implementation of Bellman-Ford algorithm in C++

Let's now dive into the implementation of the Bellman-Ford algorithm in C++. We will use an adjacency list representation of the graph and assume that the graph is stored in the form of a vector of pairs.

#include <iostream>

#include <vector>

#include <climits>

// Edge structure

struct Edge {

    int source;

    int destination;

    int weight;

};

// Function to detect negative cycles using Bellman-Ford algorithm

bool detectNegativeCycle(int vertices, const std::vector<Edge>& edges, int source) {

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

    distance[source] = 0;

    // Relax edges repeatedly

    for (int i = 1; i <= vertices - 1; ++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;

            }

        }

    }

    // Check for negative cycles

    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]) {

            return true;  // Negative cycle detected

        }

    }

    return false;  // No negative cycle found

}

int main() {

    int vertices = 4;  // Number of vertices in the graph

    // Example graph with negative cycle

    std::vector<Edge> edges = {

        {0, 1, 1},

        {1, 2, -1},

        {2, 3, -1},

        {3, 0, -1}

    };

    int source = 0;  // Source vertex

    if (detectNegativeCycle(vertices, edges, source)) {

        std::cout << "Negative cycle detected in the graph." << std::endl;

    } else {

        std::cout << "No negative cycle found in the graph." << std::endl;

    }

    return 0;

}

Code Explanation:

• We start by defining the 'Edge' structure to represent an edge in the graph. It contains the source vertex, destination vertex, and weight of the edge.
• The 'detectNegativeCycle' function takes the number of vertices, a vector of edges, and the source vertex as input.
• We initialize the distance array with 'INT_MAX' except for the source vertex, which is set to 0.
• The algorithm performs 'vertices - 1' iterations of relaxing the edges. In each iteration, it checks if updating the distance of a vertex results in a shorter path.
• After the iterations, we check for any further improvement in the distance values. If found, it means a negative cycle exists in the graph.
• Finally, in the 'main' function, we create a sample graph with a negative cycle and call the 'detectNegativeCycle' function to check if a negative cycle is present.

Example 1: Detecting a negative cycle

Let's consider a simple example to understand how the Bellman-Ford algorithm detects a negative cycle.

Graph:

0 -> 1 (1)

1 -> 2 (-1)

2 -> 3 (-1)

3 -> 0 (-1)

In this example, we have a directed graph with four vertices and four edges. There is a negative cycle from vertex 0 to vertex 3 with a total weight of -2.

Output:

Negative cycle detected in the graph.

Example 2: Negative cycle detection in a weighted graph

Consider the following graph:

Graph:

0 -> 1 (4)

0 -> 2 (3)

1 -> 2 (-2)

2 -> 3 (1)

3 -> 1 (2)

In this example, we have a directed graph with four vertices and five edges. There is no negative cycle in this graph.

Output:

No negative cycle found in the graph.

Sample Problems

Here are some sample problems related to negative cycle detection that you can try to solve using the Bellman-Ford algorithm:

• Given a weighted directed graph, write a function to detect whether it contains a negative cycle or not.
• Given a currency exchange graph, determine if there is an arbitrage opportunity (a negative cycle) that allows you to make a risk-free profit by converting currencies.
• In a transportation network, detect if there are any negative cycles representing unprofitable routes.

Conclusion

In this article, we explored the Bellman-Ford algorithm and its application in detecting negative cycles in a graph. We provided a detailed explanation of the algorithm along with its implementation in C++. We also included two examples to illustrate how the algorithm works in practice. By understanding the Bellman-Ford algorithm, you can efficiently detect negative cycles and solve various graph-related problems.