20140722

An Easy Implementation of Dijkstra's Shortest Path Algorithm.

Dijkstra's algorithm is an very easy and intuitive shortest path algorithm , it is a greedy algorithm greedy simply meaning it picks the best choices(Intermediate Shortest path here) first but this is not all about  Dijkstra's algorithm Think of it as thousands of ants dropped at a point in a maze the ants move outwards from the point in all the directions assuming they all move at same speed the first one to move out will have taken the shortest path possible .

It is interesting to note that one can see Dijkstra's Algorithm in action during lightning while the bolt searches for the path of least resistance .The Bolt finds a locally optimal choice at every point and it actually fails to find the most optimal path .



This animation from Wikipedia provides a decent explanation of how the algorithm works


This is an implementation of Dijkstra's algorithm based on following algorithm
  1. Min_Heap H /make a min heap to store vertex
  2. /returns the vertex with least weight
  3. visited[0...V] <- 0 /mark all the vertex un-visited
  4. weight[1...V] <- Infinity /path length is infinity for all nodes
  5. weight[source] <- 0
  6. previous[1...V] <- Infinity /to store actual path
  7. H.push(<weight,source>)/push source vertex in heap
  8. while(!H.isEmpty()):
  9.     u <- H.pop()
  10.     for each neighbor v of u:
  11.         new_dist <- weight[u] + graph[u-v]
  12.         /weight of path from u to v + shortest weight to reach u
  13.         if( !visited[v] ):
  14.             H.push(<v.weight,v>)
  15.             if(new_dist < weight[v])
  16.                 previous[v] <- u
  17.             weight[v] <- min(weight[v] , new_dist)
  18.            
  19.     visited[u] <- 1 /mark node visited
  20.     if(== destination_vertex):
  21.         return weight[destination_vertex]
  22. return INFINITY //if there is no way to reach destination

Here's an implementation in c++

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<iostream>
  4. #include<vector>
  5. #define INF 1<<31-1
  6. using namespace std;
  7. class min_heap{
  8.     //can also be implemented by make_heap(v.begin(), v.end(), comp);
  9.     int leaf;
  10.     vector <pair<int,int>> arr;//<weight,vertex>
  11. public:
  12.     min_heap(){
  13.         leaf=1;
  14.         arr.push_back(make_pair(0,0));
  15.     }
  16.     void push(int weight,int node){
  17.         int pvt=leaf;
  18.         if(arr.size()<=pvt)
  19.             arr.push_back(make_pair(weight,node));
  20.         else
  21.             arr[pvt]=make_pair(weight,node);
  22.         while(pvt>1){
  23.             if(arr[pvt].first<arr[pvt/2].first){
  24.                 swap(arr[pvt],arr[pvt/2]);
  25.                 pvt=pvt/2;
  26.             }
  27.             else
  28.                 break;
  29.         }
  30.         leaf++;
  31.     }
  32.     int pop(){
  33.         int ans=arr[1].second;
  34.         arr[1]=arr[leaf-1];
  35.         int elm=arr[1].first,x=1;
  36.         while(x*2+1<=leaf-1){
  37.             int exc=1,temp=arr[x].first;
  38.             //exchanging parent with the child with smaller value
  39.             if(arr[x*2].first>arr[x*2+1].first && (elm>arr[x*2].first || elm>arr[x*2+1].first )){
  40.                 swap(arr[x],arr[x*2+1]);
  41.                 x=x*2+1;
  42.                 continue;
  43.             }
  44.             if(arr[x*2].first<=arr[x*2+1].first && (elm>arr[x*2].first || elm>arr[x*2+1].first)){
  45.                 swap(arr[x],arr[x*2]);
  46.                 x=x*2;
  47.                 continue;
  48.             }
  49.             break;
  50.         }
  51.         if(leaf-1>=x*2  &&  arr[x*2].first<arr[x].first ){
  52.             swap(arr[x],arr[x*2]);
  53.         }
  54.         leaf--;
  55.         return ans;
  56.     }
  57.     bool isempty(){
  58.         if(leaf<=1)
  59.             return true;
  60.         return false;
  61.     }
  62. };
  63. class dijkstra{
  64. public:
  65.     vector <int> visited;//to mark if a vertex has been visited
  66.     vector <int> weight;//Current minimum weight to n'th node from source
  67.     vector <int> previous;//to store shortest path information
  68.     min_heap heap;
  69.     bool calculated;
  70.     int vertex;
  71. //public:
  72.     dijkstra(int vertex_cnt){
  73.         visited.resize(vertex_cnt+1,0);
  74.         weight.resize(vertex_cnt+1,INF);
  75.         previous.resize(vertex_cnt+1,INF);
  76.         calculated=false;
  77.         vertex=vertex_cnt;
  78.     }
  79.     // graph[i][0] contains the no of edges to i'th vertex
  80.     // graph[i][1...graph[i][0]] contains the vertex information connected to i'th vertex
  81.     // information structure <weight,vertex>
  82.     int shortest_path(vector <vector<pair<int,int>>> graph,int first_node,int end_node){
  83.         weight[first_node]=0;
  84.         heap.push(first_node,first_node);
  85.              
  86.         while(heap.isempty()==false){
  87.             int p_vertex=heap.pop();
  88.             for(int i=1;i<=graph[p_vertex][0].first;i++){
  89.                 int new_vertex=graph[p_vertex][i].second;//
  90.                 int new_weight=weight[p_vertex]+graph[p_vertex][i].first;
  91.                 if(visited[new_vertex]==0){
  92.                     heap.push(new_weight,new_vertex);
  93.                     if(new_weight<weight[new_vertex])
  94.                         previous[new_vertex]=p_vertex;
  95.                         //updating path if a path with less weight is found
  96.                     weight[new_vertex]=min(weight[new_vertex],new_weight);//update
  97.                 }
  98.             }
  99.             visited[p_vertex]=1;
  100.             if(p_vertex==end_node){
  101.                 calculated=true;
  102.                 return weight[end_node];
  103.             }
  104.         }
  105.         return INF;
  106.     }
  107.     //to return the actual shortest path taken in reverse
  108.     void shortest_path(vector <int> &act_path,int source,int destination){
  109.         if(calculated=false)
  110.             return;
  111.         act_path.push_back(destination);
  112.         while(destination!=source){
  113.             act_path.push_back(previous[destination]);
  114.             destination=previous[destination];
  115.         }
  116.     }
  117. };
  118. /*
  119. format of graph is an adjacency list implemented through a vector or vectors
  120. the first element of the vector contains number of edges adjacent to a node
  121. */
  122. int main()
  123. {
  124.     //freopen("input.txt","r",stdin);
  125.     vector <vector<pair<int,int>>> graph1;//A vector of vector list to contain adjacency list
  126.     graph1.push_back(vector<pair<int,int>> (1,make_pair(0,0)));
  127.     int N;
  128.     cin>>N;//number of vertex
  129.     for(int i=1;i<=N;i++){
  130.         int E;
  131.         cin>>E;//number of vertex to which i'th vertex is connected
  132.         vector <pair<int,int>> info;
  133.         info.push_back(make_pair(E,0));
  134.         for(int j=1;j<=E;j++){
  135.            
  136.             int vtx,weight;
  137.             cin>>vtx>>weight;//vertex connection and weight of that edge
  138.             info.push_back(make_pair(weight,vtx));
  139.            
  140.         }
  141.         graph1.push_back(info);
  142.     }
  143.    
  144.     int source,destination;
  145.     cin>>source>>destination;//destination
  146.     dijkstra short1(N);
  147.     cout<<"shortest distance ="<<short1.shortest_path(graph1,source,destination);
  148.     vector <int> path1;//to store actual path in reverse
  149.     short1.shortest_path(path1,source,destination);
  150.     for(int i=0;i<path1.size();i++)
  151.         cout<<path1[i]<<endl;
  152. }

Here you can find a sample input file for the above program tested in gnu's  g++ 11 compiler