Wednesday, 26 April 2017

Implementation of Dijsktra's Shortest Path Algorithm using STL

This algorithm is also called greedy technique.  This algorithm works by maintaining a set S of vertices whose shortest distance from the source is already known. Initially that set S contains only source vertex. Add each step we add a vertex to the set S whose distance from the source is short as possible. Then we can find a shortest path from the source to v that passes only through vertices in S. At each step of the algorithm, we use an array d to record the length of the shortest path to each vertex. We will use an array distance to hold the shortest distance from the source to each vertex. Implementation of Dijsktra's using STL is given below.

 The output for the above graph is shown below the program

In this program we used

1.    vector < pair<int,int> > adj_list[N]:
       we used an array of vectors of pair vectors. The first element of the pair will hold the destination of
       the edge starting from vertex adj_list[i], and second element of the pair vector will store the
       weight of the edge connecting vertex adj_list[i] to destination.


2.   visit_status[N]:-
      we used an array of n vertices, this array hold the status of each vertex i.e the shortest distance of
      vertex i from the source is finalized or not.

3.   distance[N]:-
      This array will hold the finalized shortest distance from the source to each vertex.


Algorithm 
1.  set:   distance[source]=0
2.  set the distance value infinity for every other node.
3.  create a set of all the nodes in which every node will be
    marked as unvisited.
4.  do For(v=1;v=N;v++)
5.       int u=minDistance()  /*Extract the vertex whose distance
                                is short as possible, Initially this
                                function will return the distance of
                                 source vertex
                               */
6.       Mark the vertex 'u' as visited i.e shortest distance is finalized
7.       do For(v2=1;v2<=N;v2++)
8.             if (vertex_status[v2]==unvisited &&
                     distance[v]!=infinity &&
                     distance[v]+weight(v,v2)<distance[v]):
9.                        set: distance[v2]=distance[u+weight(v,v2)
10.            end If
11.      endFor
12.  endFor


Seudocode for function minDistance()
1.   set: min=infinity
2.   declare min_index
3.   do For(v=1;v<=n;v++)
4.          If(vertex_status[v]==false && distance[v]<min)
5.                 set: min=distance[v]
6.                 set  min_index=v
7.          EndIf
8.   endFor

Time complexity: O(N^2), where N is the number of total vertices..

PROGRAM:

#include <vector>
#include <stdio.h>
#define infinity 10000000
#define MAX 100
using namespace std;

class Dijsktra_implementation
{
   private:
       std::vector< pair<int,int> > adj_list[MAX];
       std::vector< pair<int,int> >::iterator it;
       int n,distance[MAX];
       bool visit_status[MAX];
       int source;
   public:
       void get_data();
       void print();
       void dijsktra();
       int minDistance();
};
void Dijsktra_implementation::get_data()
{
   printf("\nEnter the number of vertices: ");
   scanf("%d",&n);
   int destination,weight;

   for(int i=1;i<=n;i++)
   {
         int edges;
         printf("\nEnter the number of edges starting from vertex %d: ",i);
         scanf("%d",&edges);
         if(edges!=0)
         {
             for(int j=1;j<=edges;j++)
             {
                  printf("\nEnter the destination and weight of the edge: ");
                  scanf("%d%d",&destination,&weight);
                  adj_list[i].push_back(make_pair(destination,weight));
             }
         }
   }
}
void Dijsktra_implementation::dijsktra()
{
   for(int i=1;i<=n;i++)
   {
        distance[i]=infinity;
        visit_status[i]=false;
   }

   printf("\nEnter the source to start traversal: ");
   scanf("%d",&source);

   distance[source]=0;


   for(int v=1;v<=n;v++)
   {
         int u=minDistance();

         visit_status[u]=true;

         for(it=adj_list[u].begin();it!=adj_list[u].end();it++)
         {
                   if(distance[u]!=infinity && visit_status[it->first]==false && it->second+distance[u]<distance[it->first])
                   {
                         distance[it->first]=it->second+distance[u];
                   }
         }
   }


}
int Dijsktra_implementation::minDistance()
{
   int min=infinity,min_index;
   for(int v=1;v<=n;v++)
   {
         if(distance[v]<min && visit_status[v]==false)
         {
             min=distance[v];
             min_index=v;
         }
   }
   return min_index;
}
void Dijsktra_implementation::print()
{
   printf("\n\n");
   for(int i=1;i<=n;i++)
   {
             printf("\nNode %d is connected with Node %d with weight = %d",source,i,distance[i]);
   }
}
int  main()
{
   Dijsktra_implementation graph;
   graph.get_data();
   graph.dijsktra();
   graph.print();
   return 0;
}


OUTPUT:

 


EmoticonEmoticon