CODE-2 FOR DIJKSTRA’S SHORTEST PATH ALGORITHM IN C++


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

  -> This C++ program is to implement Dijkstra’s algorithm for
     single source shortest path problem

  -> 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 dijkstra
{
private:
 int n;
 int graph[MAX][MAX];
 int colour[MAX];
 int start;
 int distance[MAX];
 int predecessor[MAX];
 enum {green,yellow,red};
public:
 void read_graph();
 void initialize();
 int select_min_distance_lable();
 void update(int);
 void output();
 void function();
};

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

 cout<<“Enter the start vertex ::”;
 cin>>start;
}

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

 for(int j=1;j<=n;j++)
 {
  if(graph[start][j]!=0)
   predecessor[j]=start;
  else
   predecessor[j]=0;
 }
}

int dijkstra::select_min_distance_lable()
{
 int min=INFINITY;
 int p=0;
 for(int i=1;i<=n;i++)
 {
  if(colour[i]==green)
  {
   if(min>=distance[i])
   {
    min=distance[i];
    p=i;
   }
  }
 }
 return  p;
}

void dijkstra::update(int p)       // p is a yellow colour node
{
 cout<<“\nupdated distances are ::\n”;
 for(int i=1;i<=n;i++)
 {
  if(colour[i]==green)
  {
   if(graph[p][i]!=0)
   {
    if(distance[i]>graph[p][i]+distance[p])
    {
     distance[i]=graph[p][i]+distance[p];
     predecessor[i]=p;
    }
   }
  }
  cout<<distance[i]<<‘\t’;
 }
}

void dijkstra::output()
{
 cout<<“****** The final paths and the distacnes are ******\n\n”;

 for(int i=1;i<=n;i++)
 {
  if(predecessor[i]==0 && i!=start)
  {
   cout<<“path does not exists between “<<i<<” and the start vertex ”
    <<start<<endl;
   exit(1);
  }
  cout<<“path for node “<<i<<” is ::\n”;
  int j=i;
  int array[MAX];
  int l=0;
  while(predecessor[j]!=0)
  {
   array[++l]=predecessor[j];
   j=predecessor[j];
  }
  for(int k=l;k>=1;k–)
   cout<<array[k]<<“->”;

  cout<<i<<endl;
  cout<<“distance is “<<distance[i]<<endl<<endl<<endl;
 }
}

void dijkstra::function()
{
 cout<<“\n**********************************************************************\n”;
 cout<<“This program is to implement dijkstra’s algorithm using colour codes \n”;
 cout<<“**********************************************************************\n\n”;
 read_graph();
 initialize();
 //repeate until all nodes become red
 int flag=0;
 int i;

 cout<<“\n\n******** The working of the algorithm is **********\n\n”;

 for(i=1;i<=n;i++)
  if(colour[i]!=red)
   flag=1;

 cout<<“The initial distances are ::\n”;
 for(i=1;i<=n;i++)
  cout<<distance[i]<<‘\t’;
 cout<<endl;

 while(flag)
 {
  int p=select_min_distance_lable();
  cout<<“\nThe min distance lable that is coloured yellow is “<<p;
  colour[p]=yellow;

  update(p);
  cout<<“\nnode “<<p<<” is coloured red “<<endl;
  colour[p]=red;

  flag=0;
  for(i=1;i<=n;i++)
   if(colour[i]!=red)
    flag=1;

  cout<<endl<<endl<<endl;
 }
 output();
}

void main()
{
 dijkstra d;
 d.function();
}

29 thoughts on “CODE-2 FOR DIJKSTRA’S SHORTEST PATH ALGORITHM IN C++”

  1. hey can u tell me whether this program gves info abt the value of the quickest path and sequence of nodes on the quickest path(i mean o/p..)

  2. thanx for the code….. but if i want to write the Dijkstra’s code for a large no. of cities then i think this code wont work….. in that case we have to use database….. if so then how?

  3. Excellent code.
    Dijkstra’s will giv the shortest path from only one source vertex to all other vertices.but, why not u try for all-pairs? Like, Can u code for Floyd’s, Dantzig’s and double-sweep all-pairs algorithm? if so, it’ll be of very help to me.

  4. it is not working
    i give the adjacency matrix and the start vertex and after that the program simply starts running and never ends leaving my pc stuck
    what is it worth ???
    !!

  5. Hi All,
    Dijkstra’s will giv the shortest path from only one source vertex to all other vertices.but, how to find out the shortest path from one source vertext to one destination vertex. i.e., Dijkstra shortest path algorithm for one to one.

  6. Dear Vinod,
    Can you example DIJKSTRA’S SHORTEST PATH ALGORITHM IN C. Because C and C++ is more different. I hope you sent my mail(keepwalking_ht@yahoo.com).
    Thank Vinod very much.
    Best and Regards !!!

  7. hiiii…
    Thanks for the illustrative Algoritm.
    Can you please implement this algorithm using link list.
    Please mail me if possible.
    Thanks a lot…..🙂

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