BELLMAN FORD’S SINGLE SOURCE SHORTEST PATH ALGORITHM


/*************************************************************************

  -> This C++ program is to implement Bellmen Ford algorithm.

  -> Bellmen Ford algorithm solves the single source shortest paths
     problem in the general case in which edge weights may be negative.

  -> This algorithm returns true if the graph contains no
     negative-weight cycles that are reachable from the source
  else returns the shortest paths from the source.

  -> This program works in Microsoft VC++ environment in windows xp

  -> Data structures used:
        Graph :: Adjacency matrix

  -> Header files used :
        1)iostream.h
 2)stdlib.h

/*************************************************************************/

#include<iostream.h>
#include<stdlib.h>

#define MAX 20
#define INFINITY 9999

class bell_ford
{
private:
 int n;
 int graph[MAX][MAX];
 int start;
 int distance[MAX];
 int predecessor[MAX];
public:
 void read_graph();
 void initialize();
 void update();
 void check();
 void algorithm();
};

void bell_ford::read_graph()
{
 cout<<“Enter the no. of nodes in the graph ::”;
 cin>>n;
 cout<<“Enter the adjacency matrix for the graph ::\n”;
 for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
   cin>>graph[i][j];
 cout<<“Enter the start vertex ::”;
 cin>>start;
}

void bell_ford::initialize()
{
 for(int i=1;i<=n;i++)
 {
   distance[i]=INFINITY;
   predecessor[i]=0;
 }
 distance[start]=0;
}

void bell_ford::update()
{
 for(int i=1;i<=n-1;i++)
 {
  for(int u=1;u<=n;u++)
  {
   for(int v=1;v<=n;v++)
   {
    if(graph[u][v]!=0)
    {
     if(distance[v]>distance[u]+graph[u][v])
     {
      distance[v]=distance[u]+graph[u][v];
      predecessor[v]=u;
     }
    }
   }
  }
 }
}

void bell_ford::check()
{
 for(int u=1;u<=n;u++)
 {
  for(int v=1;v<=n;v++)
  {
   if(graph[u][v]!=0)
   {
    if(distance[v]>distance[u]+graph[u][v])
    {
     cout<<“does not exist’s “;
     return;
    }
   }
  }
 }

 cout<<“\n\nThere is no negative weight cycle and\n”;
 cout<<“****** The final paths and the distacnes are ******\n\n”;
 for(int i=1;i<=n;i++)
 {
  cout<<“path for node “<<i<<” is ::\n”;
  int arr[MAX],k=1;
  int j=i;
  while(predecessor[j]!=0)
  {
   arr[k]=predecessor[j];
   k++;
   j=predecessor[j];
  }
  for(–k;k>0;k–)
   cout<<arr[k]<<“->”;
  cout<<i<<endl;
  cout<<“distance is “<<distance[i]<<endl<<endl<<endl;
 }
}

void bell_ford::algorithm()
{
 read_graph();
 initialize();
 update();
 check();
}

void main()
{
 bell_ford obj;
 obj.algorithm();
}

36 thoughts on “BELLMAN FORD’S SINGLE SOURCE SHORTEST PATH ALGORITHM”

  1. Pingback: TireAstoria
  2. Hi, I could not understand the following part of your program, I would be very help ful for me if you make me understand the following part

    for(k;k>0;k) //is this aiteration OK? why did you do this
    cout<<arr[k]<;
    I ahve provided my email address pls, mail me.

  3. HAI…..

    I tried your algorithm its working fine for positive values and 5 nodes…..
    once the no of nodes grows its not working……
    i tried with 20 nodes………..
    its not working……..

  4. changed
    for(-k; k>0; k-) –>> for(k=k-1; k>0; k–)
    works well, and I am very very thankful for your code! Been pleasure to use it.

    Best regards.

    1. hi
      ive replaced this,
      for(-k; k>0; k-) –>> for(k=k-1; k>0; k–)

      this gives me this error
      error C2059: syntax error : ‘)’

      please reply. thankyou

      1. hi i did again. i copy and pasted your for statement as it is! and got this error
        —————————————————————————–
        1>—— Build started: Project: beln, Configuration: Debug Win32 ——
        1>Compiling…
        1>Bln.cpp
        1>.\Beln.cpp(111) : error C2065: ‘k–’ : undeclared identifier
        —————————————————————————
        please help

      2. hi i did again. i copy and pasted your for statement as it is! and got this error
        —————————————————————————–
        1>—— Build started: Project: Beln, Configuration: Debug Win32 ——
        1>Compiling…
        1>Beln.cpp
        1>.\Beln.cpp(111) : error C2065: ‘k–’ : undeclared identifier
        —————————————————————————
        please help

        1. U seems to be absolute beginner. it is k– that means k=k-1; Any way i will send you the code that will work in a separate text file tmrw.

      3. hi,
        can anybody help me please. i want to display updated cost matrices after each update process using this code. rest is fine. code working fine but i need to display updated cost matrices.
        thanks

    2. cout<<"\n\n No negative weights are found \n";
      cout<<"****** These are the final Distances ******\n\n";
      for(int i=1;i<=Node;i++)
      {
      cout<<"path for node"<<i<0; k–);
      cout<<arr[k]<“;
      cout<<i<<endl;
      cout<<"Distance is "<<Dist[i]<<endl<<endl<—— Build started: Project: Beln, Configuration: Debug Win32 ——
      1>Compiling…
      1>Beln.cpp
      1>.\Beln.cpp(111) : error C2065: ‘k–’ : undeclared identifier
      1>Build log was saved at “file://c:\Users\riki\Documents\Downloads\Beln\Beln\Beln\Debug\BuildLog.htm”
      1>Beln – 1 error(s), 0 warning(s)
      ========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

      1. could you please send me today on curl.lyke.smoke@gmaildotcom
        moreover, i want to display adjacency matrix and update matrices. is it possible to display it? would greatly appreciate!

        Thanks for the help in advance,
        kind regards
        rakesh

  5. #include
    #include

    #define MAX 20
    #define INFINITY 9999

    class bell_ford
    {
    private:
    int n;
    int graph[MAX][MAX];
    int start;
    int distance[MAX];
    int predecessor[MAX];
    public:
    void read_graph();
    void initialize();
    void update();
    void check();
    void algorithm();
    };

    void bell_ford::read_graph()
    {
    cout<>n;
    cout<<”Enter the adjacency matrix for the graph ::\n”;
    for(int i=1;i<=n;i++)
    for(int j=1;j>graph[i][j];
    cout<>start;
    }

    void bell_ford::initialize()
    {
    for(int i=1;i<=n;i++)
    {
    distance[i]=INFINITY;
    predecessor[i]=0;
    }
    distance[start]=0;
    }

    void bell_ford::update()
    {
    for(int i=1;i<=n-1;i++)
    {
    for(int u=1;u<=n;u++)
    {
    for(int v=1;vdistance[u]+graph[u][v])
    {
    distance[v]=distance[u]+graph[u][v];
    predecessor[v]=u;
    }
    }
    }
    }
    }
    }

    void bell_ford::check()
    {
    for(int u=1;u<=n;u++)
    {
    for(int v=1;vdistance[u]+graph[u][v])
    {
    cout<<”does not exist’s “;
    return;
    }
    }
    }
    }

    cout<<”\n\nThere is no negative weight cycle and\n”;
    cout<<”****** The final paths and the distacnes are ******\n\n”;
    for(int i=1;i<=n;i++)
    {
    cout<<”path for node “<<i<0;k–)
    cout<<arr[k]<”;
    cout<<i<<endl;
    cout<<”distance is “<<distance[i]<<endl<<endl<<endl;
    }
    }

    void bell_ford::algorithm()
    {
    read_graph();
    initialize();
    update();
    check();
    }

    void main()
    {
    bell_ford obj;
    obj.algorithm();
    }

  6. Hi,
    What if we’d like to change this code to use the negative negative-weight cycles as well ?

    Let’s say we have a 3-dimensional matrix as:

    -1 2 4
    12 -1 -1
    5 8 -1

    Thanks…

  7. hi its giving me error
    “fatal error C1083: Cannot open include file: ‘iostream.h’: No such file or directory”

    i am using vc++ 2008 express edition.

  8. Are you this code implements the Bellman-Ford algorithm??..looks very much like Dijsktra’s algorithm to me..cheers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s