DJISKTRA'S ALGORITHM : SHORTEST PATH ALGORITHM

DJISKTRA'S ALGORITHM : SHORTEST PATH ALGORITHM

This algorithm is used to find shortest distance between a starting vertex and an ending vertex.Following code explains the concept:

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

This program finds the shortest path using Dijkstra’s algorithm using

Priority queue

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

#include<iostream.h>

#include<conio.h>

#define member 1

#define nomember 0

#define infinity 999

#define MAX 10

class SP

{

private:

int G[MAX][MAX],Q[MAX];

public:

int front,rear,n;

void Build_Graph();

void dikstra(int,int);

void insert_Q(int);

int Delete_Q(int);

};

void SP::Build_Graph()

{

int i,j,V1,V2;

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

{

cout<<"\n Enter the edge of V"<<i<<" to V"<<j<<": ";

cin>>G[i][j]; //read the wt of the edge

}

cout<<"\n";

}

}

void SP::insert_Q(int index)

{

Q[index]=1;//node with smallest path is inserted

}

int SP::Delete_Q(int i)

{

 if(Q[i]==1)//smallest path node

return i;

 return infinity;//if it is not a smallest path node

}

void SP::dikstra(int src,int dest)

{

int small,dist[10],current,start,new1;

int temp,i;

for(i=0;i<=n;i++)

{

Q[i]=0;

dist[i]=infinity;

}

Q[src]=1;//starting from source vertex

dist[src]=0;//initial distance is zero

current=src; //consider source node as current node

while(current!=dest)//while not reaching to dest

{

small=infinity;

start=dist[current];//start from the current node

for(i=1;i<=n;i++)

{

if(Q[i]==0)

{

new1=start+G[current][i];

if(new1<dist[i])

dist[i]=new1;

if(dist[i]<small)//finding the smallest dist

{                //from current node

small=dist[i];

temp=i;        //mark it

}

}

}

/*Priority Q is maintained for

stroing the nodes of smallest distances

from the source vertex */

current=temp;//smallest node number

insert_Q(current);//inserted in the priority Q

}

}

void main()

{

   int src,dest,path_node,k;

   SP obj;

   clrscr();

   cout<<"\n Program for shortest path algorithm using priority Queue";

   cout<<"\n Enter the number of vertices: ";

   cin>>obj.n;

   obj.Build_Graph();

   cout<<"\n Enter the source: ";

   cin>>src;

   cout<<"\n Enter the destination: ";

   cin>>dest;

   obj.dikstra(src,dest);

   cout<<"\n The Shortest path is ...\n";

   obj.front=1;obj.rear=obj.n;

   while(obj.front<=obj.rear)

    {

         path_node=obj.Delete_Q(obj.front);

         if(path_node!=infinity)

                    cout<<"    "<<path_node;//printing smallest path

          obj.front++;

    }

    getch();

}

If you have any problem in understanding the code,kindly comment and notify me and i will get back to you as soon as possible.