Shortest Path Algorithm: Dijkstra

Aim  :- To find shortest path

#include <iostream.h>

#include <conio.h>

 class graph

 {

  public:

  char a;

  char b;

  int e;

 };

 class dijkstra

 {

  public:

  int n,p,t,f;

  char c[10];

  void get_data();

  void get_connection(graph g[]);

  void shortest(graph g[]);

  void display(graph g[]);

  int minm(int [],int,char []);

  int findu(graph g[],int,int,char []);

 };

 void dijkstra::get_data()

 {

  cout<<"Enter number of nodes in your network:";

  cin>>n;

  cout<<endl<<"Write the name of each node"<<endl;

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

  {

   cout<<"Name of node "<<i+1<<":";

   cin>>c[i];

  }

 }

 void dijkstra::get_connection(graph g[])

 {

  clrscr();

  cout<<endl<<endl<<"NOW ITS TIME TO CONNECT THE NODES...!";

  cout<<endl<<"Enter 1 if there is connection between consicutive nodes otherwise enter 0"<<endl;

  p=0;

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

  {

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

   {

                cout<<c[i]<<" & "<<c[j]<<" :";

                int t;

                cin>>t;

                if(t==1)

                {

                 g[p].a=c[i];

                 g[p].b=c[j];

                 cout<<"Enter distance:";

                 cin>>g[p].e;

                 p++;

                }

   }

  }

 }

 void dijkstra::display(graph g[])

 {

  clrscr();

  cout<<"YOUR NETWORK IS LIKE THIS:"<<endl;

  for(int i=0;i<p;i++)

  {

   cout<<g[i].a<<" & "<<g[i].b<<" :"<<g[i].e<<endl;

  }

 }

 void dijkstra::shortest(graph g[])

 {

  char s,C[10];

  int q,D[10];

  cout<<endl<<endl<<"NOW ENTER NODE from which you want to find shortest distance:";

  cin>>s;

   t=0;

   f=0;

                //function to get distance & node array (Initialization)

  for(int r=0;r<n;r++)

  {

   if(s!=c[r])

   {

                C[f]=c[r];

                for(int i=0;i<p;i++)

                {

                 if((g[i].a==s && g[i].b==C[f]) || (g[i].a==C[f] && g[i].b==s))

                 {

                 D[f]=g[i].e;

                 q=0;

                 break;

                 }

                }

                if(q!=0)

                {

                D[f]=32767;

                }

                f++;

   }

  } int w,u,v;

  //greedy loop

  for(q=0;q<n-2;q++)

  {

   v=minm(D,f,C);

   for(w=0;w<f;w++)

   {

                if(C[w]!=NULL && C[w]!=C[v])

                {

                u=findu(g,w,v,C);

                D[w]=(D[w]<(u+D[v])?D[w]:(u+D[v]));

                }

   }

   C[v]=NULL;

  }

  cout<<"The sortest distance from node "<<s<<":";

  for(int z=0;z<f-1;z++)

  {

   cout<<D[z]<<",";

  }

   cout<<D[f-1];

 }

 int dijkstra::findu(graph g[],int w,int v,char C[])

 {

  for(int z=0;z<p;z++)

  {

   if((g[z].a==C[w] && g[z].b==C[v]) ||(g[z].a==C[v] && g[z].b==C[w]))

   {

                return g[z].e;

   }

  }

  return 32676;

 }

 int dijkstra::minm(int j[],int t,char c[])

 {

  int o=32766,q;

  for(int i=0;i<t;i++)

  {

   if(o>j[i] && c[i]!=NULL)

   {

                o=j[i];

                q=i;

   }

  }

  return q;

 }

 void main ()

 {

  clrscr();

  graph g[15];

  dijkstra d;

  d.get_data();

  d.get_connection(g);

  d.display(g);

  d.shortest(g);

  getch();

 }

Output: