#include <iostream>
#include <limits.h>
#include <assert.h>
#include <cstdlib>
using namespace std;
 
 
#define INF UINT_MAX //define INF as infinity value
#define locationCount 9 //define number of locations = 9
#define stack_limit 10000 //stack limit
 
typedef enum location {changi, punggol, sembawang, woodland, bukitbatok, clementi, outram, kallang, bedok, notExist};
 
const location first_location = changi;
const location last_location = bedok;
 
char* name[] = { "changi", "punggol", "sembawang", "woodland", "bukit batok", 
              "clementi", "outram", "kallang", "bedok" };
 
 
//Adjacency Matrix
unsigned int weightedGraph[locationCount][locationCount] =
{     
//       ch   pu   sem  wl   bb   cle  out  kll   bed    
        {INF, 19 , INF, INF, INF, INF, INF, INF,  10   },//changi
        {19 , INF, 17 , INF, INF, INF, INF, 17 ,  INF  },//punggol
        {INF, 17 , INF, 5  , INF, INF, INF, 22 ,  INF  },//sembawang
        {INF, INF, 5  , INF, 14 , INF, INF, 24 ,  INF  },//woodland
        {INF, INF, INF, 14 , INF, 5  , INF, 25 ,  INF  },//bukit batok
        {INF, INF, INF, INF, 5  , INF, 10 , 17 ,  INF  },//clementi
        {INF, INF, INF, INF, INF, 10 , INF, 7  ,  14   },//outram
        {INF, 17 ,  22,  24, 25 , 17 , 7  , INF,  10   },//kallang
        {10 , INF, INF, INF, INF, INF, 14,   10,  INF  } //bedok
 
};
 
 
unsigned int overEst[locationCount];
bool tight[locationCount];
location predecessor[locationCount];
 
 
location minNonTight()
{
         location i, j;
 
         for(i = first_location; i <= last_location; i+1)
         {
               if(!tight[i])
                  break;
         }
 
         assert(j <= last_location); 
 
         j = i;
 
 
         for(i+1; i<= last_location; i+1)
         {
               if(!tight[i] && overEst[i] < overEst[j])
                            j = i;      
         }
 
         return j;
}
 
 
bool successor(int i, int j)
{
     return (weightedGraph[i][j] != INF && i != j);
} 
 
 
void dijkstraAlg(location s)
{
     location i, j;  
     overEst[s] = 0;
 
     for(i = first_location; i <= last_location; i+1)
     {
           if(i != s)
                overEst[i] = INF;
 
           tight[i] = false;
           predecessor[i] = notExist;
     }
 
     for(int x = 0; x < locationCount; x++)
     {
           j = minNonTight();
           tight[j] = true;
 
           if(overEst[j] = INF)
              continue;
 
           for(i = first_location; i <= last_location; i+1)
           {
                 if(successor(i,j) && !tight[i] && 
                 overEst[j] + weightedGraph[i][j] < overEst[j])
                 {
                   overEst[i] = overEst[j] + weightedGraph[i][j];
                   predecessor[i] = j;
                 }
           }                 
 
 
 
     }     
 
}
 
 
 
/*stack for Djikstra shortest path */
 
location stack[stack_limit];
unsigned int stackTop;
 
void push(location l)
{
     assert(stackTop < stack_limit);
     stack[stackTop] = l;
     stackTop++;
 
}
 
 
location pop()
{
     stackTop--;
     return stack[stackTop];
}
 
 
bool emptyStack()
{
     return(stackTop == 0);
}
 
 
void print_shortest_path(location origin, location destination) {
 
  location v;
 
  assert(origin != notExist  &&  destination != notExist);
 
 
  dijkstraAlg(origin);
 
  cout << "The shortest path from " << name[origin] << " to " 
       << name[destination] << " :" <<endl;
 
  for (v = destination; v != origin; v = predecessor[v])
    if (v == notExist) {
      cout << "Path does not exist" << endl;
      return;
    }
    else
      push(v);
 
  push(origin); 
 
  while (!emptyStack()) 
    cout << name[pop()] << endl;
 
}
 
 
 
//MAIN
int main()
{
    int start, end;
 
    cout << "changi, punggol, sembawang, woodland, bukitbatok, clementi, outram, kallang, bedok" << endl;
 
    cout << "Enter a starting location: " << endl;
    cin >> start;
 
    cout << "Enter an ending location: " << endl;
    cin >> end;
 
    print_shortest_path((location)start, (location)end);
 
    system("pause");
 
}