Dijkstra.cpp

/***************Dijkstras shortest Path Algorithm ************************/
    #include<iostream>
    #include<list>
    #include<map>
    #include<queue>
    #include<algorithm>
    using namespace std;
    #define INF 1000
    class node{
    public:
            int self;
            int parent;
            list<int> neighbour;
            int dist;
            bool flag;    
            node(){
                cout<<"Called default constructor";
                    flag=false;
                    parent=0;
                    dist=INF;
                    }	
          
            bool operator<(const node& n)const{return n.dist < dist;}
            };
            template<typename  T>
            void print_list(T i){
                cout<<i;
            }


           int main(){
          int n;
          int p,q,w;
          cout<<"Enter the number of elements";
          cin>>n;
          node *G = new node[n];
          int **edge =new int*[n];
          for(int i=0;i<n;i++){
              edge[i]=new int[n];
              G[i].self=i;
                 		
	    }
	  cout<<"success";
          cout<<"Enter the edges spaced ";
          while(cin>>p){
              if(!p)break;	      
              cin>>q>>w;
	      p--,q--;
              edge[p][q]=w;
              edge[q][p]=w;
              G[p].neighbour.push_back(q);
	      G[q].neighbour.push_back(p);
          }

                    
    //Here comes the real fun
          cout<<"Enter the destination";
          cin>>p;//1 .. n
          p--;   //made 0 .. n-1
          
          priority_queue<node> Q;
          G[0].dist=0;
          Q.push(G[0]);
          while(!Q.empty()){
              int tmp=Q.top().self;
              Q.pop();
              G[tmp].flag=true;
              for(list<int>::iterator i=G[tmp].neighbour.begin();i!=G[tmp].neighbour.end();i++)
              {  if(!G[*i].flag){
                  cout<<"\nSelected "<<*i<<"th node";
                  if(G[tmp].dist+edge[tmp][*i] < G[*i].dist ){
                      G[*i].dist=G[tmp].dist+edge[tmp][*i];G[*i].parent=tmp;
                      cout<<"and set "<<tmp<<"as parent";
                  }
                  Q.push(G[*i]);
                }
                  
                }
              
                }
             
          cout<<"\n";
          while(p!=0){
              cout<<p+1<<"<-";
              p=G[p].parent;
          }
          cout<<1;
          
          
          
      return 0;      
      }