# Bellman-Ford Algorithm – Shortest Distance with Negative Edge

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

DisclaimerDon’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:

## C++ 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;
}

Output:
0 5 3 3 1 2

Time Complexity: O(N*E). We check E edges N times

Space Complexity: O(N). Distance Array

## Java Code

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>();

Main obj = new Main();