C Program to find Shortest Path using Bellman Ford Algorithm

By | 05.07.2017

Shortest Path using Bellman Ford Algorithm


Write a C Program to find Shortest Path using Bellman Ford Algorithm. 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 Distances or Path using Dijkstra’s algorithm

Below is the source code for C Program to find Shortest Path using Bellman Ford Algorithm which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :


/* C Program to find Shortest Path 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

int n;    /*Number of vertices in the graph*/
int adj[MAX][MAX]; /*Adjacency Matrix*/

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);
int BellmanFord(int s);

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( );
        pathLength[s] = 0; /*Make pathLength of source vertex 0*/
        insert_queue(s); /*Insert the source vertex in the queue*/
    isPresent_in_queue[s] = TRUE;
        while( !isEmpty_queue( ) )
        {
                current = delete_queue( );
                isPresent_in_queue[current] = FALSE;
                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 )
                                if( pathLength[i] > pathLength[current] + adj[current][i] )
                                {
                                        pathLength[i] = pathLength[current] + adj[current][i];
                                        predecessor[i] = current;
                                        if( !isPresent_in_queue[i] )
                                        {
                                                insert_queue(i);
                                                isPresent_in_queue[i]=TRUE;
                                        }
                                }
                }
        }
        return 1;
}/*End of BellmanFord()*/

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 create_graph()
{
        int i,max_edges,origin,destin, wt;

        printf("\nEnter number of vertices : ");
        scanf("%d",&n);
        max_edges=n*(n-1);

        for(i=1;i<=max_edges;i++)
        {
                printf("\nEnter edge %d( -1 -1 to quit ) : ",i);
                scanf("%d %d",&origin,&destin);

                if( (origin == -1) && (destin == -1) )
                        break;

                printf("\nEnter weight for this edge : ");
                scanf("%d",&wt);

                if( origin >= n || destin >= n || origin<0 || destin<0)
                {
                        printf("\nInvalid edge!\n");
                        i--;
                }
                else
                        adj[origin][destin] = wt;
        }
}

OUTPUT : :


/* C Program to find Shortest Path using Bellman Ford Algorithm */

Enter number of vertices : 6

Enter edge 1( -1 -1 to quit ) : 0 1

Enter weight for this edge : 3

Enter edge 2( -1 -1 to quit ) : 0 2

Enter weight for this edge : 4

Enter edge 3( -1 -1 to quit ) : 0 3

Enter weight for this edge : -2

Enter edge 4( -1 -1 to quit ) : 1 3

Enter weight for this edge : 1

Enter edge 5( -1 -1 to quit ) : 3 4

Enter weight for this edge : 5

Enter edge 6( -1 -1 to quit ) : 2 5

Enter weight for this edge : -3

Enter edge 7( -1 -1 to quit ) : -1 -1

Enter source vertex : 0

Enter destination vertex(-1 to quit): 1

Shortest Path is : 0  1
 Shortest distance is : 3

Enter destination vertex(-1 to quit): 2

Shortest Path is : 0  2
 Shortest distance is : 4

Enter destination vertex(-1 to quit): 3

Shortest Path is : 0  3
 Shortest distance is : -2

Enter destination vertex(-1 to quit): 4

Shortest Path is : 0  3  4
 Shortest distance is : 3

Enter destination vertex(-1 to quit): 5

Shortest Path is : 0  2  5
 Shortest distance is : 1

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 up to you in short interval.


Thanks for reading the post…


Recommended Posts : :

0 0 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments