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;
}

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.