Problem Statement: Given a weighted directed graph with negative edge weights with n nodes and m edges. Nodes are labeled from 0 to n-1, the task is to find the shortest distance from the source node to all other nodes. Output “-1” if there exists a negative edge weight cycle in the graph.
Note: edges[i] is defined as u, v and weight.

Examples:

Example 1:

Input:
Edges : [[0,1,5],[1,5,-3],[1,2,-2],[2,4,3],[3,2,6],[3,4,-2],[5,3,1]]

Output: [0,5,3,3,1,2]



Explanation: The shortest distance is calculated pretty much like the Djisktra’s Algorithm except that we have negative edge weights year. 
For node pair 0-4 the possible paths were 0->1->2->4(cost = 6) and 0->1->5->3->4(cost = 1). We choose the minimum of these two of cost = 1. In the same manner, the costs for other nodes are calculated.
Note that since no negative edge weight cycle exists, our output is an array with minimum distance to all other nodes from source node 0. 

Example 2:

Input:
Edges : [[0,1,1],[1,2,-1],[2,3,-1],[3,0,-1]]

Output: -1

Explanation: Notice that the graph has a negative edge weight cycle. 0->1->2->3(cost = -2). Hence, we output -1 to indicate the same.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Why Djikstra’s doesn’t work?

The answer is plain and simple. The presence of negative edge weights makes the situation dicey. Djikstra’s algorithm might work in some cases and fail in some. Consider the following example:

Recall that in Dijkstra’s algorithm, we update the distance array every time we find a better solution which was a lesser distance. With the presence of negative edge weights, our algorithm would continue to update the distance array with lesser and lesser values and we might end up in time limit exceeded or segmentation fault error. Try to dry run the following example and you would understand the issue yourself.

Intuition: We would try to update our distance array in a somewhat same manner as we did in Dijkstra’s algorithm. However, we need to handle the negative edge weights as well. Thus, we need to update the array in a controlled fashion may be, a specific number of times. Remember, we don’t want to end up in an endless loop.

Approach:

1. We would use a technique what is known as “Relaxing Edges” wherein we would update our distance array if we find a better solution. We would do this N-1 times. 
2. Now why N-1? Understand that for a given graph with N nodes, the maximum number of edges we could have between any two nodes is N-1 in a single path. Moreover, our adjacency list might be in such a manner that only one node is updated in a single pass. Thus, to try out all nodes, we would require atleast N-1 iterations.The following is the demonstration of the same:

Code:

#include<bits/stdc++.h>
using namespace std;
struct node {
    int u;
    int v;
    int wt; 
    node(int first, int second, int weight) {
        u = first;
        v = second;
        wt = weight;
    }
};

int main(){
    int N=6,m=7;
    vector<node> edges; 
	edges.push_back(node(0,1,5));
	edges.push_back(node(1,2,-2));
	edges.push_back(node(1,5,-3));
	edges.push_back(node(2,4,3));
	edges.push_back(node(3,2,6));
	edges.push_back(node(3,4,-2));
	edges.push_back(node(5,3,1));
    int src=0;
    int inf = 10000000; 
    vector<int> dist(N, inf); 
    dist[src] = 0; 
    for(int i = 1;i<=N-1;i++) {
        for(auto it: edges) {
            if(dist[it.u] + it.wt < dist[it.v]) {
                dist[it.v] = dist[it.u] + it.wt; 
            }
        }
    }

    int fl = 0; 
    for(auto it: edges) {
        if(dist[it.u] + it.wt < dist[it.v]) {
            cout << -1; 
            fl = 1; 
            break; 
        }
    }
    
    if(!fl) {
        for(int i = 0;i<N;i++) {
            cout << dist[i]<<" ";
        }
    }
    return 0;
}

import java.util.*; 

class Node 
{
	private int u;
    private int v;
    private int weight;
    
    Node(int _u, int _v, int _w) { u = _u; v = _v; weight = _w; }
    
    Node() {}
    
    int getV() { return v; }
    int getU() { return u; }
    int getWeight() { return weight; }

}
 

class Main
{
    void bellmanFord(ArrayList<Node> edges, int N, int src)
    {
        int dist[] = new int[N];
        for(int i = 0;i<N;i++) dist[i] = 10000000; 

        dist[src] = 0;

    	for(int i = 1;i<=N-1;i++) {
    		for(Node node : edges) {
    			if(dist[node.getU()] + node.getWeight() < dist[node.getV()]) {
    				dist[node.getV()] = dist[node.getU()] + node.getWeight(); 
    			}
    		}
    	}

    	int fl = 0; 
    	for(Node node: edges) {
    		if(dist[node.getU()] + node.getWeight() < dist[node.getV()]) {
    			fl = 1;
    			System.out.println("Negative Cycle"); 
    			break;
    		}
    	}

    	if(fl == 0) {
    		for(int i = 0;i<N;i++) {
    			System.out.print(  dist[i]+" "); 
    		}
    	}
    }
    public static void main(String args[])
    {
        int n = 6;
        ArrayList<Node> adj = new ArrayList<Node>();
		
			
		adj.add(new Node(3, 2, 6));
		adj.add(new Node(5, 3, 1));
		adj.add(new Node(0, 1, 5));
		adj.add(new Node(1, 5, -3));
		adj.add(new Node(1, 2, -2));
		adj.add(new Node(3, 4, -2));
		adj.add(new Node(2, 4, 3));

	
		Main obj = new Main(); 
		obj.bellmanFord(adj, n, 0);
		
    }
}

Special thanks to Naman Daga for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article