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.
No comments:
Post a Comment
Thanks for your valuable comment