Shortest path problem is problem of finding shortest path from given particular point/vertex to all other points or vertices in a graph. Bellman Ford algorithm is used for this purpose specially in the case of negative edge weight/weights in a graph. The only limitation of this algorithm is “graph should not contain negative edge weight cycles”, however the Bellman Ford algorithm can be used to detect negative edge cycles in graph.

Negative edge cycle example

Shortest path problem with negative weights  Bellman Ford algorithm

The above example graph contains a negative cycle in it. The negative  cycle is (2>3>4>2) because total sum of edge weight  becomes negative (-2 + 3 -3 ) = -2 . As in above graph the distance from (vertex 0) to (vertex 2) is 3 but if we go through the cycle (2>3>4>2) once , the total cost to reach from (vertex 0) to (vertex 2) will reduce to ( 3 -2 ) = 1. if we go through the cycle in second time the total cost to reach from (vertex 0) to (vertex 2) will become (1 – 2) = -1, which is less than the previous cost. if we continue to go through the cycle again and again then after each iteration cost to travel from (vertex 0) to (vertex 2) will reduced. In this case it is impossible to reach from (vertex 0) to (vertex 3).

Bellman Ford algorithm

Shortest path problem with negative weights  Bellman Ford algorithm

Sample code Shortest path problem with negative weights  Bellman Ford algorithm

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

#define NODES 6
#define INF 9999
void bellmanFord(int G[NODES][NODES], int source);
int main() {
	// Adjacency Matrix of above graph
	int G[NODES][NODES] = {
			{ 0, 5, 3, 0, 0, 4 },
			{ 0, 0, 0, 7, 0, 0 },
			{ 0, 0,0, -2, 0, 0 },
			{ 8, 0, 0, 0, 3, 0 },
			{ 0, 0, 2, 0, 0, 6 },
			{ 0, 0,0, 0, 0, 0 } };
	// run Bellman Ford algo on graph Graph G
	bellmanFord(G, 0);

	return 0;
}

void bellmanFord(int G[NODES][NODES], int s) {
	int i = 0;
	//distance
	int dist[NODES];

	/************************************************/
	/* step 1 */
	/************************************************/

	// initialization inifinity distance from source to
	// destination
	for (i = 0; i < NODES; i++) {
		dist[i] = INF;
	}
	// initialize 0 distance to source vertex
	dist[s] = 0;

	/************************************************/
	/* step 2 */
	/************************************************/
	int u = 0;
	int v = 0;
	int p = 0;
	for (p = 0; p < NODES - 1; p++) {
		// process all edges
		for (u = 0; u < NODES; u++) {
			for (v = 0; v < NODES; v++) {
				if (G[u][v] && (dist[v] > dist[u] + G[u][v]))
					dist[v] = dist[u] + G[u][v];
			}
		}
	}
	/************************************************/
	/* step 3 detect negative cycle */
	/************************************************/

	for (p = 0; p < NODES - 1; p++) {
		for (u = 0; u < NODES; u++) {
			for (v = 0; v < NODES; v++) {
				if (G[u][v] && (dist[v] > dist[u] + G[u][v])) {
					printf("There is negative edge cycle in graph\n");
					exit(1);
				}
			}
		}
	}
	// print distance
	for (i = 0; i < NODES; ++i)
		printf("Node %d\t", i);
	printf("\n--------------------------------------\n");
	for (i = 0; i < NODES; ++i)
		printf("%d\t", dist[i]);

	printf("\n");
}

Output:

Node 0    Node 1    Node 2    Node 3    Node 4    Node 5
———————————————————————–
0             5             3             1              4             4




Related Contents to follow