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");
    
}

by the way this is my main when I run the program for testing

int main()
{ 
    print_shortest_path(changi, bedok);

    system("pause");
    
}

If this is a duplicate forgive me. I posted but it didn't show up!

This is a mistake! It's in two places in your code!

//         for(i = first_location; i <= last_location; i+1)
         for(i = first_location; i <= last_location; i++)

i+1 is not an expression! Use either i++ or i+= 1

for(i+1; i<= last_location; i+1)
              ^                        ^

Also set 0's as your diagonal when source=destination!

i++ or i+= will not work because the compiler doesnt allow such operations for enum iterations

i++ or i+= will not work because the compiler doesnt allow such operations for enum iterations

what do you mean. Isn't 'i' a int variable declared inside the for loop?

Enum math isn't available so you have to do a work around.

You have to use integers for the loop, but cast it into the enum!

for( int i = first_location; i <= last_location; i++)
     {
         location eLoc = static_cast <location> (i);
            or
         location eLoc = (location) i;


     }
This article has been dead for over six months. Start a new discussion instead.