a flightmap path finding algorithm

  adt, c++, path-finding, stack

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++

LEAVE A COMMENT