DEV Community

Cover image for Negative cycle with Dijskta(Possible but not optimal)
Priya Pandey
Priya Pandey

Posted on

Negative cycle with Dijskta(Possible but not optimal)

I decided to experiment with Dijkstra’s algorithm to solve a problem that may involve negative cycles. While Dijkstra’s algorithm isn't optimal for graphs with negative weights, I found that it can be adapted with some modifications.

Thought Process Behind Using Dijkstra's Algorithm for Negative Cycles:

The core issue with negative cycles is that they can lead to continuously decreasing distances, causing incorrect results. Normally, Dijkstra's algorithm works by updating the distance to a node when a shorter path is found, which happens within an 'if' block that compares the new distance to the previously calculated one. However, with a negative cycle, this comparison will keep returning true because the total distance keeps decreasing as we go around the cycle.

To handle this, my approach stores the paths for each node. The next time we visit a node, we check whether the node itself is already part of the path leading to it. If the node is found in its own path, it indicates a cycle. This means we are revisiting the node through a cycle that potentially decreases the distance, leading us into the if block where we detect the negative cycle. On the other hand, if we find a shorter path that doesn’t form a cycle, the node's distance is updated as usual.

Here’s my code implementation, which adapts Dijkstra’s algorithm while incorporating path tracking:

vector<int> bellman_ford(int V, vector<vector<int>>& edges, int S) {
    vector<vector<pair<int,int>>> adj(V);
    for(int i=0;i<edges.size();i++){
        adj[edges[i][0]].push_back({edges[i][1],edges[i][2]});
    }
    vector<int> dist(V,1e8);
    dist[S] = 0;
    vector<vector<int>> path(V);
    path[S] = {S};
    queue<pair<int,int>> q;
    q.push({S,0});

    while(!q.empty()) {
        int node = q.front().first;
        int dis = q.front().second;
        q.pop();

        for(auto it: adj[node]) {
            if(dis + it.second < dist[it.first]) {
                vector<int> temp = path[node];

                // Check if the node is already in its path (cycle detection)
                if(find(temp.begin(), temp.end(), it.first) != temp.end()) {
                    return {-1}; // Negative cycle detected
                }

                temp.push_back(it.first);
                path[it.first] = temp;
                q.push({it.first, dis + it.second});
                dist[it.first] = dis + it.second; // Update distance
            }
        }
    }
    return dist;
}
Enter fullscreen mode Exit fullscreen mode

This approach ensures that the block is entered only when a reducing distance is detected, either due to a linear path or a negative cycle. If a cycle is found in the path, the function returns -1 to indicate the presence of a negative cycle. Otherwise, it updates the distance accordingly.

Let me know your thoughts on this.

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay