Shortest Paths using Bellman-Ford Algorithm
Write a C Demo Program to find Shortest Paths using Bellman-Ford Algorithm Example. Here’s a simple C Program to find Shortest Distances or Paths using Bellman-Ford Algorithm with output in C Programming Language.
Bellman-Ford Algorithm
The Bellman-Ford algorithm is a graph search algorithm that finds the shortest path between a given source vertex and all other vertices in the graph. This algorithm can be used on both weighted and unweighted graphs.
Like Dijkstra’s shortest path algorithm, the Bellman Ford algorithm is guaranteed to find the shortest path in a graph. Though it is slower than Dijkstra’s algorithm, Bellman-Ford is capable of handling graphs that contain negative edge weights, so it is more versatile.
It is worth noting that if there exists a negative cycle in the graph, then there is no shortest path. Going around the negative cycle an infinite number of times would continue to decrease the cost of the path (even though the path length is increasing). Because of this, Bellman-Ford can also detect negative cycles which is a useful feature.
Also Read : C Program to find Shortest Path using Bellman Ford Algorithm
Below is the source code for C Program to find Shortest Paths using Bellman Ford Algorithm which is successfully compiled and run on Windows System to produce desired output as shown below :
SOURCE CODE : :
/* Demo Program to find shortest paths using Bellman-Ford algorithm */
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
#define infinity 9999
#define NIL -1
#define TRUE 1
#define FALSE 0
#define STOP getchar( )
int n; /*Number of vertices in the graph*/
int adj[MAX][MAX]; /*Adjacency Matrix*/
int BellmanFord(int s);
int predecessor[MAX];
int pathLength[MAX];
int isPresent_in_queue[MAX];
int front,rear;
int queue[MAX];
void initialize_queue( );
void insert_queue(int u);
int delete_queue();
int isEmpty_queue();
void create_graph( );
void findPath(int s, int v);
void displayTable();
void display_queue();
int main()
{
int flag,s,v;
create_graph();
printf("\nEnter source vertex : ");
scanf("%d",&s);
flag = BellmanFord(s);
if(flag == -1)
{
printf("\nError : negative cycle in Graph\n");
exit(1);
}
while(1)
{
printf("\nEnter destination vertex(-1 to quit): ");
scanf("%d",&v);
if(v == -1)
break;
if(v < 0 || v >= n )
printf("\nThis vertex does not exist\n");
else if(v == s)
printf("\nSource and destination vertices are same\n");
else if( pathLength[v] == infinity )
printf("\nThere is no path from source to destination vertex\n");
else
findPath(s,v);
}
return 0;
}/*End of main()*/
void findPath(int s, int v )
{
int i,u;
int path[MAX]; /*stores the shortest path*/
int shortdist = 0; /*length of shortest path*/
int count = 0; /*number of vertices in the shortest path*/
/*Store the full path in the array path*/
while( v != s )
{
count++;
path[count] = v;
u = predecessor[v];
shortdist += adj[u][v];
v = u;
}
count++;
path[count]=s;
printf("\nShortest Path is : ");
for(i=count; i>=1; i--)
printf("%d ",path[i]);
printf("\n Shortest distance is : %d\n", shortdist);
}/*End of findPath()*/
int BellmanFord(int s)
{
int k = 0,i,current;
for(i=0;i<n;i++)
{
predecessor[i] = NIL;
pathLength[i] = infinity;
isPresent_in_queue[i] = FALSE;
}
initialize_queue( );
printf("\nMake pathLength of source vertex 0\n");
pathLength[s] = 0; /*Make pathLength of source vertex 0*/
printf("\nInsert source vertex in the queue\n");
insert_queue(s); /*Insert the source vertex in the queue*/
isPresent_in_queue[s] = TRUE;
display_queue();
displayTable( );
STOP;
while( !isEmpty_queue( ) )
{
current = delete_queue( );
isPresent_in_queue[current] = FALSE;
printf("\nCurrent vertex is %d\n",current);
if(s == current)
k++;
if(k > n )
return -1;/*Negative cycle reachable from source vertex*/
for(i=0;i<n;i++)
{
if ( adj[current][i] != 0 )
{
printf("\nVertex %d is adjacent to current vertex %d\n", i, current);
if( pathLength[i] > pathLength[current] + adj[current][i] )
{
printf("pathLength(%d) + weight(%d,%d) < pathLength(%d)\t",current,current,i,i);
printf("%d + %d < %d\n",pathLength[current],adj[current][i],pathLength[i]);
pathLength[i] = pathLength[current] + adj[current][i];
predecessor[i] = current;
printf("\nRelabel vertex %d\n",i);
printf("\npathLength[%d] = %d , ",i, pathLength[i]);
printf("\npredecessor[%d] = %d\n",i,current);
if( !isPresent_in_queue[i] )
{
insert_queue(i);
isPresent_in_queue[i] = TRUE;
printf("\nInsert %d in the queue\n\n",i);
}
else
printf("%d is present in the queue\n\n",i);
}
else
{
if( pathLength[current] + adj[current][i] == pathLength[i] )
{
printf("pathLength(%d) + weight(%d,%d) = pathLength(%d)\t",current,current,i,i);
printf("%d + %d = %d\n",pathLength[current],adj[current][i],pathLength[i]);
}
else
{
printf("pathLength(%d) + weight(%d,%d) > pathLength(%d)\t",current,current,i,i);
printf("%d + %d > %d\n",pathLength[current],adj[current][i],pathLength[i]);
}
printf("\nDon't Relabel vertex %d\n\n",i);
}
}
}
display_queue();
displayTable( );
STOP;
}
return 1;
}/*End of BellmanFord()*/
void displayTable()
{
int i;
printf("\nVertex pathLength Predecessor\n");
for(i=0;i<n;i++)
{
printf("%d\t%d\t\t", i, pathLength[i]);
if( predecessor[i] == NIL )
printf("NIL\n");
else
printf("%d\n", predecessor[i]);
}
printf("\n\n");
}/*End of displayTable()*/
void initialize_queue( )
{
int i;
for(i=0;i<MAX;i++)
queue[i] = 0;
rear = -1;front = -1;
}/*End of initailize_queue()*/
int isEmpty_queue()
{
if(front == -1 || front>rear )
return 1;
else
return 0;
}/*End of isEmpty_queue()*/
void insert_queue(int added_item)
{
if (rear == MAX-1)
{
printf("\nQueue Overflow\n");
exit(1);
}
else
{
if (front == -1) /*If queue is initially empty */
front = 0;
rear = rear+1;
queue[rear] = added_item ;
}
}/*End of insert_queue()*/
int delete_queue()
{
int d;
if (front == -1 || front > rear)
{
printf("\nQueue Underflow\n");
exit(1);
}
else
{
d = queue[front];
front = front+1;
}
return d;
}/*End of delete_queue() */
void display_queue()
{
int i;
if ( isEmpty_queue() )
{
printf("\nQueue is empty\n");
return;
}
printf("\nQUEUE : ");
for(i=front;i<=rear;i++)
printf("%d ",queue[i]);
printf("\n\n");
}/*End of display_queue()*/
/*Graph given in book figure 7.55*/
void create_graph()
{
n = 8;
adj[0][1] = 8;
adj[0][2] = 9;
adj[0][4] = 7;
adj[1][5] = 9;
adj[2][0] = 5;
adj[2][1] = -4;
adj[2][3] = 3;
adj[3][1] = 3;
adj[3][2] = 6;
adj[3][5] = 4;
adj[4][7] = 16;
adj[5][0] = 4;
adj[5][6] = -8;
adj[5][7] = 5;
adj[6][3] = 5;
adj[6][7] = 2;
}
/*
void create_graph()
{
int i,max_edges,origin,destin, wt;
printf("Enter number of vertices : ");
scanf("%d",&n);
max_edges=n*(n-1);
for(i=1;i<=max_edges;i++)
{
printf("Enter edge %d( -1 -1 to quit ) : ",i);
scanf("%d %d",&origin,&destin);
if( (origin == -1) && (destin == -1) )
break;
printf("Enter weight for this edge : ");
scanf("%d",&wt);
if( origin >= n || destin >= n || origin<0 || destin<0)
{
printf("Invalid edge!\n");
i--;
}
else
adj[origin][destin] = wt;
}
}
*/
OUTPUT : :
/* Demo Program to find shortest paths using Bellman-Ford algorithm */ Enter source vertex : 0 Make pathLength of source vertex 0 Insert source vertex in the queue QUEUE : 0 Vertex pathLength Predecessor 0 0 NIL 1 9999 NIL 2 9999 NIL 3 9999 NIL 4 9999 NIL 5 9999 NIL 6 9999 NIL 7 9999 NIL Current vertex is 0 Vertex 1 is adjacent to current vertex 0 pathLength(0) + weight(0,1) < pathLength(1) 0 + 8 < 9999 Relabel vertex 1 pathLength[1] = 8 , predecessor[1] = 0 Insert 1 in the queue Vertex 2 is adjacent to current vertex 0 pathLength(0) + weight(0,2) < pathLength(2) 0 + 9 < 9999 Relabel vertex 2 pathLength[2] = 9 , predecessor[2] = 0 Insert 2 in the queue Vertex 4 is adjacent to current vertex 0 pathLength(0) + weight(0,4) < pathLength(4) 0 + 7 < 9999 Relabel vertex 4 pathLength[4] = 7 , predecessor[4] = 0 Insert 4 in the queue QUEUE : 1 2 4 Vertex pathLength Predecessor 0 0 NIL 1 8 0 2 9 0 3 9999 NIL 4 7 0 5 9999 NIL 6 9999 NIL 7 9999 NIL Current vertex is 1 Vertex 5 is adjacent to current vertex 1 pathLength(1) + weight(1,5) < pathLength(5) 8 + 9 < 9999 Relabel vertex 5 pathLength[5] = 17 , predecessor[5] = 1 Insert 5 in the queue QUEUE : 2 4 5 Vertex pathLength Predecessor 0 0 NIL 1 8 0 2 9 0 3 9999 NIL 4 7 0 5 17 1 6 9999 NIL 7 9999 NIL Current vertex is 2 Vertex 0 is adjacent to current vertex 2 pathLength(2) + weight(2,0) > pathLength(0) 9 + 5 > 0 Don't Relabel vertex 0 Vertex 1 is adjacent to current vertex 2 pathLength(2) + weight(2,1) < pathLength(1) 9 + -4 < 8 Relabel vertex 1 pathLength[1] = 5 , predecessor[1] = 2 Insert 1 in the queue Vertex 3 is adjacent to current vertex 2 pathLength(2) + weight(2,3) < pathLength(3) 9 + 3 < 9999 Relabel vertex 3 pathLength[3] = 12 , predecessor[3] = 2 Insert 3 in the queue QUEUE : 4 5 1 3 Vertex pathLength Predecessor 0 0 NIL 1 5 2 2 9 0 3 12 2 4 7 0 5 17 1 6 9999 NIL 7 9999 NIL Current vertex is 4 Vertex 7 is adjacent to current vertex 4 pathLength(4) + weight(4,7) < pathLength(7) 7 + 16 < 9999 Relabel vertex 7 pathLength[7] = 23 , predecessor[7] = 4 Insert 7 in the queue QUEUE : 5 1 3 7 Vertex pathLength Predecessor 0 0 NIL 1 5 2 2 9 0 3 12 2 4 7 0 5 17 1 6 9999 NIL 7 23 4 Current vertex is 5 Vertex 0 is adjacent to current vertex 5 pathLength(5) + weight(5,0) > pathLength(0) 17 + 4 > 0 Don't Relabel vertex 0 Vertex 6 is adjacent to current vertex 5 pathLength(5) + weight(5,6) < pathLength(6) 17 + -8 < 9999 Relabel vertex 6 pathLength[6] = 9 , predecessor[6] = 5 Insert 6 in the queue Vertex 7 is adjacent to current vertex 5 pathLength(5) + weight(5,7) < pathLength(7) 17 + 5 < 23 Relabel vertex 7 pathLength[7] = 22 , predecessor[7] = 5 7 is present in the queue QUEUE : 1 3 7 6 Vertex pathLength Predecessor 0 0 NIL 1 5 2 2 9 0 3 12 2 4 7 0 5 17 1 6 9 5 7 22 5 Current vertex is 1 Vertex 5 is adjacent to current vertex 1 pathLength(1) + weight(1,5) < pathLength(5) 5 + 9 < 17 Relabel vertex 5 pathLength[5] = 14 , predecessor[5] = 1 Insert 5 in the queue QUEUE : 3 7 6 5 Vertex pathLength Predecessor 0 0 NIL 1 5 2 2 9 0 3 12 2 4 7 0 5 14 1 6 9 5 7 22 5 Current vertex is 3 Vertex 1 is adjacent to current vertex 3 pathLength(3) + weight(3,1) > pathLength(1) 12 + 3 > 5 Don't Relabel vertex 1 Vertex 2 is adjacent to current vertex 3 pathLength(3) + weight(3,2) > pathLength(2) 12 + 6 > 9 Don't Relabel vertex 2 Vertex 5 is adjacent to current vertex 3 pathLength(3) + weight(3,5) > pathLength(5) 12 + 4 > 14 Don't Relabel vertex 5 QUEUE : 7 6 5 Vertex pathLength Predecessor 0 0 NIL 1 5 2 2 9 0 3 12 2 4 7 0 5 14 1 6 9 5 7 22 5 Current vertex is 7 QUEUE : 6 5 Vertex pathLength Predecessor 0 0 NIL 1 5 2 2 9 0 3 12 2 4 7 0 5 14 1 6 9 5 7 22 5 Current vertex is 6 Vertex 3 is adjacent to current vertex 6 pathLength(6) + weight(6,3) > pathLength(3) 9 + 5 > 12 Don't Relabel vertex 3 Vertex 7 is adjacent to current vertex 6 pathLength(6) + weight(6,7) < pathLength(7) 9 + 2 < 22 Relabel vertex 7 pathLength[7] = 11 , predecessor[7] = 6 Insert 7 in the queue QUEUE : 5 7 Vertex pathLength Predecessor 0 0 NIL 1 5 2 2 9 0 3 12 2 4 7 0 5 14 1 6 9 5 7 11 6 Current vertex is 5 Vertex 0 is adjacent to current vertex 5 pathLength(5) + weight(5,0) > pathLength(0) 14 + 4 > 0 Don't Relabel vertex 0 Vertex 6 is adjacent to current vertex 5 pathLength(5) + weight(5,6) < pathLength(6) 14 + -8 < 9 Relabel vertex 6 pathLength[6] = 6 , predecessor[6] = 5 Insert 6 in the queue Vertex 7 is adjacent to current vertex 5 pathLength(5) + weight(5,7) > pathLength(7) 14 + 5 > 11 Don't Relabel vertex 7 QUEUE : 7 6 Vertex pathLength Predecessor 0 0 NIL 1 5 2 2 9 0 3 12 2 4 7 0 5 14 1 6 6 5 7 11 6 Current vertex is 7 QUEUE : 6 Vertex pathLength Predecessor 0 0 NIL 1 5 2 2 9 0 3 12 2 4 7 0 5 14 1 6 6 5 7 11 6 Current vertex is 6 Vertex 3 is adjacent to current vertex 6 pathLength(6) + weight(6,3) < pathLength(3) 6 + 5 < 12 Relabel vertex 3 pathLength[3] = 11 , predecessor[3] = 6 Insert 3 in the queue Vertex 7 is adjacent to current vertex 6 pathLength(6) + weight(6,7) < pathLength(7) 6 + 2 < 11 Relabel vertex 7 pathLength[7] = 8 , predecessor[7] = 6 Insert 7 in the queue QUEUE : 3 7 Vertex pathLength Predecessor 0 0 NIL 1 5 2 2 9 0 3 11 6 4 7 0 5 14 1 6 6 5 7 8 6 Current vertex is 3 Vertex 1 is adjacent to current vertex 3 pathLength(3) + weight(3,1) > pathLength(1) 11 + 3 > 5 Don't Relabel vertex 1 Vertex 2 is adjacent to current vertex 3 pathLength(3) + weight(3,2) > pathLength(2) 11 + 6 > 9 Don't Relabel vertex 2 Vertex 5 is adjacent to current vertex 3 pathLength(3) + weight(3,5) > pathLength(5) 11 + 4 > 14 Don't Relabel vertex 5 QUEUE : 7 Vertex pathLength Predecessor 0 0 NIL 1 5 2 2 9 0 3 11 6 4 7 0 5 14 1 6 6 5 7 8 6 Current vertex is 7 Queue is empty Vertex pathLength Predecessor 0 0 NIL 1 5 2 2 9 0 3 11 6 4 7 0 5 14 1 6 6 5 7 8 6 Enter destination vertex(-1 to quit): 4 Shortest Path is : 0 4 Shortest distance is : 7 Enter destination vertex(-1 to quit): 1 Shortest Path is : 0 2 1 Shortest distance is : 5 Enter destination vertex(-1 to quit): 2 Shortest Path is : 0 2 Shortest distance is : 9 Enter destination vertex(-1 to quit): 3 Shortest Path is : 0 2 1 5 6 3 Shortest distance is : 11 Enter destination vertex(-1 to quit): 4 Shortest Path is : 0 4 Shortest distance is : 7 Enter destination vertex(-1 to quit): 5 Shortest Path is : 0 2 1 5 Shortest distance is : 14 Enter destination vertex(-1 to quit): 6 Shortest Path is : 0 2 1 5 6 Shortest distance is : 6 Enter destination vertex(-1 to quit): 7 Shortest Path is : 0 2 1 5 6 7 Shortest distance is : 8 Enter destination vertex(-1 to quit): -1 Process returned 0
If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach out to you in short interval.
Thanks for reading the post…
Recommended Posts : :
- Topological Sorting Algorithm Example
- Minimum Spanning Tree using Kruskal’s Algorithm
- Minimum Spanning Tree using Prim’s Algorithm
- Shortest Path using Bellman Ford Algorithm