I am doing a program to print out the shortest path between locations. I implemented it using a 2D array for the adjacency matrix.
However, when I run it and input the start and end locations, nothing else happens.
#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");
}