// The follwoing is a quick and dirty program to implement
// dijkstra's shortest path algorithm
// The example is from Carrano

// Just to show some of the syntax

void printpath(int, int[]);

#include <vector>
#include <queue>
#include <iostream>
const int MAX = 5;
const int Inf = 99;  // infinity
using namespace std;

class edge
{
  public :
    edge(int d, int v1, int v2):weight(d), vertex1(v1), vertex2(v2){};
    bool operator > ( const edge & right)const { return weight > right.weight;}
    int weight;
    int vertex1;
    int vertex2;
};
// need to define a > operator so can use a priority queue of them
// needs a way of comparing them

int main()
{
   priority_queue <edge, vector<edge>, greater<edge>  >pq;
//  declaring a priority queue of edge - stipulating greater so
//  it orders on a min-heap i.e. pq.top() will be smallest weight
//  edge in pq

  int parent[] = {0,0,0,0,0};

  int a[MAX][MAX] = { 0,8,Inf,9,4,
                      Inf,Inf,1,Inf,Inf,
                      Inf,2,Inf,3,Inf,
                      Inf,Inf,2,Inf,7,
                      Inf,Inf,1,Inf,Inf} ;

     
  bool inVertexSet[MAX]= {true,false,false,false,false};
  int weights[MAX];
  for (int i = 0; i < MAX; i++)
     weights[i] = a[0][i];  // first row of matrix
  
  for (int i = 0; i < MAX ; i++)
     pq.push (edge( a[0][i],i,0));
  
  while (!pq.empty())
  {
     edge p = pq.top();
     int dist = p.weight;
     int v = p.vertex1;
     pq.pop();
     if (!inVertexSet[v])
     { 
         inVertexSet[v] = true;
         for (int u=0; u< MAX; u++)
         {
            if (!inVertexSet[u])
               if (weights[u] >= weights[v]+a[v][u])
               {
                   weights[u] = weights[v] + a[v][u];
                   // need to keep track of path here
                   // by recording u's parent as v
                   parent[u] = v;
                   pq.push(edge(weights[u],u,v));
               }
         }
     }
     for (int i=0;i<MAX;i++)
        cout << weights[i] << '\t';
     cout << endl;
  }
  cout << "The shortest weights from 0 to each vertex are: \n";
  for (int i=0;i<MAX;i++)
  {
     cout << "\nDISTANCE to "<<  i << " = " << weights[i] << endl;
     cout << "PATH from 0 to vertex " << i << endl;
     printpath(i,parent);
     cout << endl;
     system("pause");
  }
}
 

// prints shortest path from vertex 0 to vertex i
// recursive function so can print from source to destination
void printpath(int i,  int parent[])
{
    if (i !=0)
    {
        printpath(parent[i],parent);
        cout << i << '\t';
    }
    else cout<<'\n' << i  << '\t';
}