C++/c++

Advertisement


Question
could u pls help mi,i realli need your help.i dun knw which part of the code is wrong.when I input the start and end locations, there will be an error appear.

code:
#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 << "**************************Singapore Routes*************************\n" << endl;
  cout << "changi, punggol, sembawang, woodland, bukit batok, clementi, outram" << endl;
  cout << "kallang, bedok\n" << endl;

   cout << "Enter a starting location: ";
   cin >> start;
   
   cout << "Enter an ending location: ";
   cin >> end;
  
   print_shortest_path((location)start, (location)end);

   system("pause");
   
}  

Answer
There are several logical errors in your program - they would have generated compiler diagnostics, which you should pay attention to:

char* name[] = {"changi", "punggol", "sembawang", "woodland", "bukit batok",
         "clementi", "outram", "kallang", "bedok"};

Literal strings in C++ are not modifiable. The above should be

const char* name[] = {"changi", "punggol", "sembawang", "woodland", "bukit batok",
         "clementi", "outram", "kallang", "bedok"};

There are errors in your for loops. i+1 does not increment i.
If i is an int, to increment i write either ++i or i = i + 1 ;
If i is an enum, say location, there is no ++ or + operator. You need to write i = location( i + 1 ) ;



for example, in function minNonTight, the loop increment is incorrect

location minNonTight()
{
       location i, j;

       for(i = first_location; i <= last_location; i+1) // *** here
       {
         if(!tight[i])
         break;
       }

       assert(j <= last_location);

       j = i;


       for(i+1; i<= last_location; i+1) // *** here
       {
         if(!tight[i] && overEst[i] < overEst[j])
         j = i;
       }

       return j;
}

It should be

location minNonTight()
{
       location i, j;

       for(i = first_location; i <= last_location; i = location( i + 1 ) ) // *** modified
       {
         if(!tight[i])
         break;
       }

       assert(j <= last_location);

       j = i;


       for( i = location( i + 1 ) ; i<= last_location; i = location( i + 1 ) ) // *** modified
       {
         if(!tight[i] && overEst[i] < overEst[j])
         j = i;
       }

       return j;
}

In function void dijkstraAlg(location), the same problem exists in the two for loops:

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

should be

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


Also in the same function,

         if(overEst[j] = INF) // *** use == to compare for equality
         continue;

should be

         if(overEst[j] == INF) // *** use == to compare for equality
         continue;


In addition,

#include <limits.h>
#include <assert.h>

There are no such headers in standard C++. Instead use,

#include <climits>
#include <cassert>

Make these modifications, compile, and then test your program.  

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


vijayan

Expertise

my primary areas of interest are generic and template metaprogramming, STL, algorithms, design patterns and c++11. i would not answer questions about gui and web programming.

Experience

about 15 years or so

Education/Credentials
post graduate engineer

©2016 About.com. All rights reserved.