Demo Example to find Shortest Paths using Bellman-Ford Algorithm

By | 14.07.2017

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

0 0 votes
Article Rating
Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments