Expert: Joseph Moore - 8/31/2009

Question
could u pls help mi,i need your help.i don't knw which part of the code is wrong.i can't seems to print out the path.

code:
#include <iostream>
#include <cstdlib>
#include <climits>
#include <cassert>

using namespace std;


#define oo UINT_MAX /* infinity is represented as the maximum unsigned int. */
#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;

const 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    
  {oo,  19,  oo,  oo,  oo,  oo,  oo,  oo,   10 },//changi
  {19,  oo,  17,  oo,  oo,  oo,  oo,  17,   oo },//punggol
  {oo,  17,  oo,  5,   oo,  oo,  oo,  22,   oo },//sembawang
  {oo,  oo,  5,   oo,  14,  oo,  oo,  24,   oo },//woodland
  {oo,  oo,  oo,  14,  oo,  5,   oo,  25,   oo },//bukit batok
  {oo,  oo,  oo,  oo,  5,   oo,  10,  17,   oo },//clementi
  {oo,  oo,  oo,  oo,  oo,  10,  oo,  7,    14 },//outram
  {oo,  17,  22,  24,  25,  17 , 7,   oo,   10 },//kallang
  {10,  oo,  oo,  oo,  oo,  oo,  14,  10,   oo } //bedok
};


unsigned int overEst[locationCount];
bool tight[locationCount];
location predecessor[locationCount];


location minNonTight()
{
        location i, j;
        
        
        for(i = first_location; i <= last_location; i = location(i + 1))
        {     
              if(!tight[i])
                 break;
        }
              
        j = i;
        assert(j <= last_location);
               
        for(i = location(i + 1); i<= last_location; i = location(i + 1))
        {
              if(!tight[i] && overEst[i] < overEst[j])
                
                           j = i;      
        }
        
        return j;
}


bool successor(int i, int j)
{
    return (weightedGraph[i][j] != oo && i != j);
}


void dijkstraAlg(location s)
{
    location i, j;  
    overEst[s] = 0;
    
    for(i = first_location; i <= last_location;i = location( i + 1 ))
    {
          if(i != s)
               overEst[i] = oo;
           
          tight[i] = false;
          predecessor[i] = notExist;
    }
    
    for(int x = 0; x < locationCount; x++)
    {
          j = minNonTight();
          tight[j] = true;
          
          if(overEst[j] == oo)
             continue;
        
          for(i = first_location; i <= last_location;i = 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;
       char option;
       
       while (option != 'q')//start of while loop
       {
           cout << endl;
           cout << "**************************Singapore Routes*************************\n" << endl;
           cout << endl;
           cout << "MENU\n";
           cout << "****\n";
           cout << "(a) Display list of locations\n";
           cout << "(b) Enter starting and ending location\n";
           cout << "(q) Quit the program\n";
           cout << endl;
           cout << "Your selection is: ";
           cin >> option;
           cout << endl;
           cin.clear();
           cin.ignore(80,'\n');
           
       
       
           switch (option)
           {
               
               case 'a': cout << "List of locations" << endl;
                           cout << endl;
                         cout << "0-changi\n";
                         cout << "1-punggol\n";
                         cout << "2-sembawang\n";
                         cout << "3-woodland\n";
                         cout << "4-bukit batok\n";
                         cout << "5-clementi\n";
                         cout << "6-outram\n";
                         cout << "7-kallang\n";
                         cout << "8-bedok\n" << endl;  
                         break;
               case 'b': cout << "Enter starting location: ";
                         cin >> start;
                         cout << "Enter ending location: ";
                         cin >> end;
                         print_shortest_path((location)start, (location)end);
                         break;
               case 'q': cout << "End of program!!!" << endl;            
                         break;
               default :
                         cout << endl;
                         break;
           }
    
       }
       system("pause");
       
       return 0;  
}  

Answer
Hi, Isabella.

You are so, so, so very close with your code.

The first thing you need to do is to change your while loop in the main function to a do/while loop:

   while (option != 'q')//start of while loop
   {
       ... body of loop
   }

...needs to become...

   do
   {
       ... body of loop
   } while (option != 'q');

This is because the variable "option" isn't initialized until the very first input by the user, so looping on the variable is unsafe unless the loop has been executed at least once.  This is probably the most common use of the do/while loop versus the while loop -- responding to user input inside a while loop.

That's just semantics, though.  What you're really interested in is the problem with your program logic.  Prior to this, I was not familiar with Dijkstra's algorithm, actually.  I had to look it up. :)  Your logic is all sound, except that you're using the wrong variable in one spot, and that causes the whole thing to fail.

The general logic for determining if the distance currently being checked is shorter than the distance already recorded when going through the graph nodes is something like:

   distanceToCurrent + distanceFromCurrentToConnecting < distanceToConnecting

In your code, though, you're using the wrong subscript on an array, so it reads more like:

   distanceToCurrent + distanceFromCurrentToConnecting < distanceToCurrent

The above statement will never be true unless a distance is negative (a physical impossibility).  The problem is in the second for loop of the dijkstraAlg function.  I've highlighted the problem code below:

   void dijkstraAlg(location s)
   {
       location i, j;  
       overEst[s] = 0;

       for(i = first_location; i <= last_location;i = location( i + 1 ))
       {
           if(i != s)
               overEst[i] = oo;
          
           tight[i] = false;
           predecessor[i] = notExist;
       }
   
       for(int x = 0; x < locationCount; x++)
       {
           j = minNonTight();
           tight[j] = true;
         
           if(overEst[j] == oo)
               continue;
       
           for(i = first_location; i <= last_location;i = location(i + 1))
           {
               if(successor(i,j) && !tight[i] &&
               overEst[j] + weightedGraph[i][j] < overEst[j]) //// <<< THE PROBLEM IS HERE
               {
                   overEst[i] = overEst[j] + weightedGraph[i][j];
                   predecessor[i] = j;
               }
           }                 
       }     
   }

You see the line I've highlighted (with a comment)?  The code you wrote is this:

   overEst[j] + weightedGraph[i][j] < overEst[j]

The code needs to, instead, read:

   overEst[j] + weightedGraph[i][j] < overEst[i]

Notice that the variable in the []'s on the second overEst is i instead of j.  I will say that this is a good example of poor variable naming (sorry).  If the variables were named more appropriately, something such as "currentNode" and "connectingNode" or similar, then the mistake would be more obvious, because it would read:

   overEst[currentNode] + weightedGraph[currentNode][connectingNode] < overEst[currentNode]

You can see that it is more obvious that you are using the current node on both sides of the test, instead of currentNode on one side and connectingNode on the other.  As it stands, they are just "i" and "j" -- meaningless variables that even look similar on screen.  I think that technically, the i and j in the weightedGraph section ought to be reversed, as well.  In fact, I reversed it in my example of changed variable names above.  However, so long as the connections cost the same going both ways, it isn't an issue.

OK, hopefully that answers all your questions.  If you have any further questions, do not hesitate to ask.  I'm here to help. :)