Detecting negative cycle using Bellman Ford algorithm

In this tutorial we will be using Bellman Ford algorithm to detect negative cycle in a weighted directed graph. Bellman Ford algorithm is useful in finding shortest path from a given source vertex to all the other vertices even if the graph contains a negative weight edge. And Bellman Ford algorithm is also used to detect if a graph contains a negative cycle.

What is a Negative cycle?

A negative cycle in a weighted graph is a cycle whose total weight is negative.

Lets see two examples.

Conside the following graph.

Weight of the graph is equal to the weight of its edges.
So, weight = 1 + 2 + 3
= 6

Positive value, so we don’t have a negative cycle.

Let us consider another graph.

Weight of the graph is equal to the weight of its edges.
So, weight = 3 + 2 + (-6)
= -1

Negative value, so we have a negative cycle.

Problem

Consider the following graph with negative weight edge.

Source vertex for the above graph is 0

Notations we will use are given below.
u = start vertex
v = end vertex
u --> v = directed edge from vertex u to v
w(u,v) = weight of the directed edge u --> v

Our first task is to write down the edges of the graph along with the weight.

Point to note

• If there are N vertices then we will iterate N - 1 times to get the shortest distance.
• And we do the Nth iteration to check if there is any negative cycle.

The graph has 4 vertices so we will iterate 3 times to find shortest distance. And we will perform the 4th iteration to check if there is any negative cycle.

We will need a distance array d[ ] which will hold the distance to the respective vertices from the source vertex. And a predecessor array p[ ] which will hold the predecessor of the respective vertices. Both the array will be of size N (total number of vertices).

Steps

Step 1: We start by filling the distance array d[ ] with INFINITY and since vertex 0 is the source vertex so we will set d[0] = 0.

Step 2: Next we will fill the predecessor array p[ ] with 0.

Step 3: We will relax all the edges of the graph by loop N-1 times.

Step 4: We will perform the Nth loop to check if the graph has any negative cycle.

About Relaxing Edge

Consider an edge u --> v where u is the start and v is the end vertex respectively. Relaxing an edge relax(u,v) means to find shorter path to reach v when considering edge u --> v

relax(u,v)
if v.d > u.d + w(u,v) then
  v.d = u.d + w(u,v)
  v.p = u

where
v.d = distance from source vertex 0 to vertex v
u.d = distance from source vertex 0 to vertex uw(u,v) = weight of the edge u --> v
v.p = predecessor of vertex v

So, if there exists a better path to reach vertex v then, we update the distance and predecessor of vertex v.

Why perform the Nth loop

After completing iteration (N-1) we get the shortest distance. Now in order to check if there is no negative cycle we have to perform the Nth iteration.

If there is no change in the value of distance array d[ ] in the Nth loop then the graph has no negative cycle which means we can find the shortest path. Otherwise the graph has negative cycle and we cannot find the shortest path as

Solution

After performing (N-1)th loop we will get the following distance array d[ ].

And the following predecessor array p[ ].

On performing the Nth loop we will get a change in value in the distance array d[ ] which means a negative cycle exists and hence we cannot compute the shortest paths.

Code in C

#include <stdio.h>
#include <stdlib.h>

#define INFINITY 99999

//struct for the edges of the graph
struct Edge {
  int u;  //start vertex of the edge
  int v;  //end vertex of the edge
  int w;  //weight of the edge (u,v)
};

//Graph - it consists of edges
struct Graph {
  int V;  //total number of vertices in the graph
  int E;  //total number of edges in the graph
  struct Edge *edge;  //array of edges
};

void bellmanford(Graph *g, int source);
void display(int arr[], int size);

int main(void) {
  //create graph
  struct Graph *g = (struct Graph*)malloc(sizeof(struct Graph));
  g->V = 4;  //total vertices
  g->E = 5;  //total edges
  
  //array of edges for graph
  g->edge = (struct Edge*)malloc(g->E * sizeof(struct Edge));
  
  //------- adding the edges of the graph
  /*
    edge(u, v)
    where   u = start vertex of the edge (u,v)
        v = end vertex of the edge (u,v)
    
    w is the weight of the edge (u,v)
  */
  
  //edge 0 --> 1
  g->edge[0].u = 0;
  g->edge[0].v = 1;
  g->edge[0].w = 5;
  
  //edge 0 --> 2
  g->edge[1].u = 0;
  g->edge[1].v = 2;
  g->edge[1].w = 4;

  //edge 1 --> 3
  g->edge[2].u = 1;
  g->edge[2].v = 3;
  g->edge[2].w = 3;

  //edge 2 --> 1
  g->edge[3].u = 2;
  g->edge[3].v = 1;
  g->edge[3].w = -6;

  //edge 3 --> 2
  g->edge[4].u = 3;
  g->edge[4].v = 2;
  g->edge[4].w = 2;
  
  bellmanford(g, 0);    //0 is the source vertex
  
  return 0;
}

void bellmanford(Graph *g, int source) {
  //variables
  int i, j, u, v, w;

  //total vertex in the graph g
  int tV = g->V;
  
  //total edge in the graph g
  int tE = g->E;
  
  //distance array
  //size equal to the number of vertices of the graph g
  int d[tV];
  
  //predecessor array
  //size equal to the number of vertices of the graph g
  int p[tV];
  
  //step 1: fill the distance array and predecessor array
  for (i = 0; i < tV; i++) {
    d[i] = INFINITY;
    p[i] = 0;
  }
  
  //mark the source vertex
  d[source] = 0;
  
  //step 2: relax edges |V| - 1 times
  for(i = 1; i <= tV-1; i++) {
    for(j = 0; j < tE; j++) {
      //get the edge data
      u = g->edge[j].u;
      v = g->edge[j].v;
      w = g->edge[j].w;
      
      if(d[u] != INFINITY && d[v] > d[u] + w) {
        d[v] = d[u] + w;
        p[v] = u;
      }
    }
  }
  
  //step 3: detect negative cycle
  //if value changes then we have a negative cycle in the graph
  //and we cannot find the shortest distances
  for(i = 0; i < tE; i++) {
    u = g->edge[i].u;
    v = g->edge[i].v;
    w = g->edge[i].w;
    if(d[u] != INFINITY && d[v] > d[u] + w) {
      printf("Negative weight cycle detected!\n");
      return;
    }
  }
  
  //No negative weight cycle found!
  //print the distance and predecessor array
  printf("Distance array: ");
  display(d, tV);
  printf("Predecessor array: ");
  display(p, tV);
}

void display(int arr[], int size) {
  int i;
  for(i = 0; i < size; i ++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

Time complexity

Bellman Ford algorithm has a time complexity of O(VE) where V is the total number of vertices in the graph and E is the total number of edges in the graph.