11 th Experiment DIJKSTRA's ALGORITHM SHORTEST PATH

ALGORITHM FOR DJIKSTRA'S ALG:

Step-1: Start.

Step-2: Create the class dij with its object d.

Step-3: Call the member function process().

Step-4: Read the number of vertices and the adjacency matrix and the source vertex.

Step-5: Do the process by calling the member function mndist() and distcal()

Step-6: Display the shortest path.

Step-7: Stop.

---------------------------------------------------------------------------------------------------------------------------------------
                                                                        FLOWCHARTs
---------------------------------------------------------------------------------------------------------------------------------------

--------------------------------------------------------------------------------------------------------------------------------------
                                                                     C++ IMPLEMENTATION
-------------------------------------------------------------------------------------------------------------------------------------



//program for SHORTEST PATH by DIJKSTRA's ALGORITHM
#include<iostream.h>
#include<conio.h>
class dij
{
private:
int i,j,num,m1,m2,n,u,sou,min;
int p[10],p1[10],s[10],dist[10],s1[10],mat[10][10];
public:
void process();
void display();
void distcal();
void mindist();
};
void dij::process()
{
cout<<"\n ENTER NO OF VERTICES...?\n";
cin>>n;
cout<<"\n ENTER THE ADJACENCY MATRIX...:\n";
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>mat[i][j];
}
}
cout<<"\n ENTER THE SOURCE VERTEX...;\n";
cin>>sou;
for(i=1;i<=n;i++)
{
s[i]=0;
p1[i]=sou;
dist[i]=mat[sou][i];
}
s[sou]=1;
s1[i]=sou;
p[sou]=0;
num=2;
while(num<=n)
{
mindist();
cout<<"\n THE NEXT VERTEX SELECTED IS...:"<<sou+1;
s[u]=1;
s1[num]=u;
p[u]=p1[u];
distcal();
num++;
}
display();
}
void dij::mindist()
{
i=1;
while(s[i]!=0)
i++;
min=dist[i];
u=i;
for(j=j+1;j<=n;j++)
{
if((s[j]==0) && (min>dist[j]))
{
min=dist[j];
u=j;
}
}
}
void dij::distcal()
{
int m1,m2,u1,u;
for(i=1;i<=n;i++)
{
if(s[i]==0)
{
m1=mat[sou][i];
u1=sou;
for(j=2;j<=num;j++)
{
u=s1[j];
if(mat[u][i]==2000)
m2=2000;
else
m2=dist[u]+mat[u][i];
if(m1>m2)
m1=m2;
u1=u;
dist[i]=m1;
p1[i]=u1;
}
}
}
}
void dij::display()
{
int i,k,root[10];
cout<<"\n\t\t\tSHORTEST PATH\n";
cout<<"\t\t      ~~~~~~~~~~~~~~~~~~~~\n";
cout<<"\t\t  THE ENTERED ADJACENCY MATRIX IS...:\n";
cout<<"\n   source \t destination \t distance\n\n\n";
for(i=1;i<=n;i++)
{
if(i!=sou)
{
j=1;u=i;
while(p[u]!=sou)
{
root[j]=p[u];
j++;
u=p[u];
}
cout<<"       "<<sou<<"\t\t"<<i<<"\t\t"<<dist[i]<<"\t\t";
cout<<sou<<"->";
for(int k=j-1;k>=1;k--)
cout<<root[k]<<"->";
cout<<i<<"\n";
}
}
}
//---------------MAIN FUNCTION-----------------------
void main()
{
clrscr();
cout<<"\t\t\t   DIJKSTRA's ALGORITHM \n";
cout<<"\t\t           ~~~~~~~~~~~~~~~~~~~~~\n";
dij d;
d.process();
getch();
}

-------------------------------------------------------
OUTPUT
------------------------------------------------------
ENTER THE NO OF VERTEX:
 3
ENTER THE ADJACENCY MATRIX...:
2 5 8
1 5 8
2 5 8
ENTER THE SOURCE VERTEX...: 1
NEXT VERTEX SELECTED IS...: 2
NEXT VERTEX SELECTED IS...: 3


                  SHORTEST PATH
                          ~~~~~~~~~~~~~~~

source destination distance
  1    2    5 1->2
  1    3    8 1->2->3