currently a homework that I am working on aims to simulate a flightMap system that has reads cities and flights from a txt file and that has a main searching algorithm that finds paths from a departure city to a destination city through flights. The non-recursive search algorithm that uses stack adt that I wrote finds only some of the ways that a person can go from A to B. The problem is that when the program visits a city, it marks it as visited = true so that next time it is encountered, it is skipped. However, there are
different paths that lead to a middle city (lets call it C), which leads directly to the destination city. Yet the program already marked C as visited, so skips it and presents only one pathway as the outcome. If I make it visited = false, then the program infinitely tries the same pathway since C is unvisited each time. My current code is given below. Thank you for your help.
CityStack* cityStack = new CityStack(citySize); // current cityStack
CityStack** flightArray = new CityStack * [flightSize]; // array of cityStacks which is the list of pathways
int stackNumber = 0; // number of pathways
cityStack->push(getCity(deptCity));
getCity(deptCity)->setVisited(true);
//I begin with the first city as deptCity
while (!cityStack->isEmpty()) {
if (cityStack->getTop() != destCity)
{
if (checkFlightToUnvisitedCities(getCity(cityStack->getTop()))) {
//here I am marking the city as visited and pushing it to the stack
City*& unvisited = getUnvisitedDestCity(getCity(cityStack->getTop()));
cityStack->push(unvisited);
unvisited->setVisited(true);
}
else
{
//I pop the city to backtrack
cityStack->pop();
}
}
else
{
//I create a copy cityStack to add to the array of cityStack as a working pathway
flightArray[stackNumber] = new CityStack(cityStack);
stackNumber++;
//I set the destination city ass visited = false;
getCity(cityStack->getTop())->setVisited(false);
//I used to pop twice to go back and not get into infinite loop because destination city visited = false
cityStack->pop();
cityStack->pop();
}
}
Source: Windows Questions C++