Get Widget

Bellman Ford Algorithm to find shortest path

In our previous post,  Dijkstra Algorithm, we calculated the shortest path from a single source to all destinations (vertices) on a graph with non-negative weights. In this post, we will study an algorithm for single source shortest path on a graph with negative weights but no negative cycles.
Here are some points to keep in mind regarding the different algorithms studied so far:
  1. Breadth First Search : For graphs where the edge-weights are either zero or all same.
  2. Dijkstra's Alogrithm : For graphs where the edge-weights are non-negative. Uses greedy strategy.
  3. Bellman-Ford Algorithm : For graphs where the edge-weights may be negative, but no negative weight cycle exists. Uses dynamic programming.
This post contains array - based implementation for simplicity. Another way is to use linked lists using dynamic allocation. 

An example graph taken from Introduction to Algorithms :


The code in C is as follows. Its time complexity is O (VE).


#include <stdio.h>
#include <stdlib.h>
int Bellman_Ford(int G[20][20] , int V, int E, int edge[20][2])
{
    int i,u,v,k,distance[20],parent[20],S,flag=1;
    for(i=0;i<V;i++)
        distance[i] = 1000 , parent[i] = -1 ;
        printf("Enter source: ");
        scanf("%d",&S);
        distance[S-1]=0 ;
    for(i=0;i<V-1;i++)
    {
        for(k=0;k<E;k++)
        {
            u = edge[k][0] , v = edge[k][1] ;
            if(distance[u]+G[u][v] < distance[v])
                distance[v] = distance[u] + G[u][v] , parent[v]=u ;
        }
    }
    for(k=0;k<E;k++)
        {
            u = edge[k][0] , v = edge[k][1] ;
            if(distance[u]+G[u][v] < distance[v])
                flag = 0 ;
        }
        if(flag)
            for(i=0;i<V;i++)
                printf("Vertex %d -> cost = %d parent = %d\n",i+1,distance[i],parent[i]+1);

        return flag;
}
int main()
{
    int V,edge[20][2],G[20][20],i,j,k=0;
    printf("BELLMAN FORD\n");
    printf("Enter no. of vertices: ");
    scanf("%d",&V);
    printf("Enter graph in matrix form:\n");
    for(i=0;i<V;i++)
        for(j=0;j<V;j++)
        {
            scanf("%d",&G[i][j]);
            if(G[i][j]!=0)
                edge[k][0]=i,edge[k++][1]=j;
        }

    if(Bellman_Ford(G,V,k,edge))
        printf("\nNo negative weight cycle\n");
    else printf("\nNegative weight cycle exists\n");
    return 0;
}
It's output on the above graph is:
Share on Google Plus
Cyber Lingo is a multi-topic blog focussing primarily on computer science and technology.
    Blogger Comment
    Facebook Comment

3 comments:

  1. This is an awesome algorithm. I also found another good and complete code for Bellman Ford Algorithm in C Programming.

    ReplyDelete
  2. How you printed execution time in program?

    ReplyDelete
    Replies
    1. The execution time is not a part of the program, it is printed by default by the Codeblocks IDE. It is not required by the program, and is not indicative of the complexity as well.

      Delete