Infinite loop when trying to find the shortest path in a graph

Question

I have adapted the below code to fit my needs for finding the paths in a graph

//H-File
#include<iostream>
#include <list>
using namespace std;
#ifndef _Graph__
#define _Graph__


class Graph
{
    int V; // No. of vertices in graph
    list<int> *adj; // Pointer to an array containing adjacency lists

    // A recursive function used by printAllPaths()
    void printAllPathsUtil(int , int , bool [], int [], int &);

public:
    Graph(int V); // Constructor
    void addEdge(int u, int v);
    void printAllPaths(int s, int d);
};

void solveMaze(string name, int start, int end);



#endif /* defined(__Graph__) */

    //CPP FILE
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int u, int v)
{
    adj[u].push_back(v); // Add v to u’s list.
}

// Prints all paths from 's' to 'd'
void Graph::printAllPaths(int s, int d)
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];

    // Create an array to store paths
    int *path = new int[V];
    int path_index = 0; // Initialize path[] as empty

    // Initialize all vertices as not visited
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Call the recursive helper function to print all paths
    printAllPathsUtil(s, d, visited, path, path_index);
}


void Graph::printAllPathsUtil(int u, int d, bool visited[], int path[], int &path_index){
    // Mark the current node and store it in path[]
    visited[u] = true;
    path[path_index] = u;
    path_index++;

    // If current vertex is same as destination, then print
    // current path[]
    if (u == d)
    {
        int steps;
        for (int i = 0; i<path_index; i++){
            cout << path[i] << " ";
            steps = i;
        }

        cout << endl;
        cout << "Length of path is " << steps << endl;
    }
    else // If current vertex is not destination
    {
        // Recur for all the vertices adjacent to current vertex
        list<int>::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
            if (!visited[*i])
                printAllPathsUtil(*i, d, visited, path, path_index);
    }

    // Remove current vertex from path[] and mark it as unvisited
    path_index--;
    visited[u] = false;
}

void solveMaze(string name, int start, int end){
    vector<int> graphData;
    ifstream f(name);
    if (f.is_open()) {
        string line;
        getline(f, line);
        char c;
        while (f >> c) {
            if (c == '1') {
                graphData.push_back(1);
            }
            else if (c =='0') {
                graphData.push_back(0);
            }
        }
        f.close();
    }


    int numRooms = int(graphData.size()/4);
    int numCols = sqrt(graphData.size()/4);
    cout << "numCols: " << numCols << endl;
    cout << "rooms: "<< numRooms << endl;
    cout << endl;
    cout << endl;

    Graph maze(numRooms);
    for(int room = 0; room < numRooms; ++room){
        //if room is on top row and left corner
        if(room == 0){

            if(graphData[(room*4+1)] == 1){//You are at room 0, checking room 1
                maze.addEdge(room, room+1);
                cout << "a ";
                cout << "room " << room << " to " << room+1 << endl;
            }
            if(graphData[(room*4+2)] == 1){//Checking below room zero
               maze.addEdge(room, room+numCols);
                cout << "b ";
                cout << "room " << room << " to " << room+numCols << endl;
            }
        }

        //if room is on top row
        if(room < numCols && room !=0){
            if(graphData[(room*4+1)] == 1){//Check to east
                maze.addEdge(room, room+1);
                cout << "c ";
                cout << "room " << room << " to " << room+1 << endl;
            }
            if(graphData[(room*4+2)] == 1){//Checking to south
                maze.addEdge(room, room+numCols);
                cout << "d ";
                cout << "room " << room << " to " << room+numCols << endl;
            }

        }

        //if room is on top row and right corner
        if(room == numCols-1){
            if(graphData[(room*4+2)] == 1){//Checking to south
                maze.addEdge(room, room+numCols);
                cout << "e ";
                cout << "room " << room << " to " << room+numCols << endl;
            }

        }
        //if room is on middle row and left room
        if((room >= numCols) && (room%numCols == 0)){
            if(graphData[(room*4+1)] == 1){//Check to east
                maze.addEdge(room, room+1);
                cout << "f ";
                cout << "room " << room << " to " << room+1 << endl;
            }
            if(graphData[(room*4+2)] == 1){//Checking to south
                maze.addEdge(room, room+numCols);
                cout << "g ";
                cout << "room " << room << " to " << room+numCols << endl;
            }

        }

        //if room is on middle row and right room
        if((room > numCols) && (room%numCols == numCols-1)){
            if(graphData[(room*4+2)] == 1){//Checking to south
                maze.addEdge(room, room+numCols);
                cout << "h ";
                cout << "room " << room << " to " << room+numCols << endl;
            }

        }

        //if room is on bottom row but not the room on the right corner
        if(room > numCols && (room == numRooms-numCols)){
            if(graphData[(room*4+1)] == 1){//Check to east
                maze.addEdge(room, room+1);
                cout << "i ";
                cout << "room " << room << " to " << room+1 << endl;
            }

        }
        //else room is just in middle rows
        if((room > numCols) && (room%numCols != numCols-1) && (room%numCols != 0)){
            if(graphData[(room*4+1)] == 1){//Check to east
                maze.addEdge(room, room+1);
                cout << "j ";
                cout << "room " << room << " to " << room+1 << endl;
            }
            if(graphData[(room*4+2)] == 1){//Checking to south
                maze.addEdge(room, room+numCols);
                cout << "k ";
                cout << "room " << room << " to " << room+numCols << endl;
            }

        }
    }
    cout << endl;
    cout << endl;
    cout << "Finding all paths from " << start << " to " << end << "..." << endl;

    maze.printAllPaths(start, end);
}

It is working pretty nicely except for when I have a situation where I hit a dead end in the graph and have to circle back. It continues to take the same path so it gets stuck in an infinite loop. I am not sure how I can combat this issue. Just to be clear: if I have a connection like

A--B--C--D--E
   |
   F

It will travel from A to B to F and then back to B then to F repeatedly. I would like it to travel from A to B to F then back to B then to C. Any ideas?

Off topic: the include guards should surround the whole header file. Placing stuff above `#ifndef _Graph__` that has the potential to give you grief. `_Graph__` is an illegal identifier because of the double underscore. [More on that linked here](https://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier). Placing `using namespace std` in a header leaves a particularly nasty surprise for other coders. — user4581301, Aug 06 '17 at 16:42
This code is missing a bunch of headers and a `main` function which duplicates the reported problem. — user4581301, Aug 06 '17 at 16:46
OK...at first glance you are missing at least a couple of compiler directives: #include and #include...If I was your compiler I would be arguing with you too. You seem to be abusing 'getline' in a way that I have never seen before and I kind of like that because it is new and refreshing but it won't work. Read up on using 'getline' or accomplish the business in another way. — Dr t, Aug 06 '17 at 16:47
Now I see that you also need #include...You also have what looks like a TON of type conversion problems...What compiler allowed you to compile and run this mess???? — Dr t, Aug 06 '17 at 16:47

Beta · Accepted Answer · 2017-08-06T22:22:10.407

In printAllPathsUtil:

// Recur for all the vertices adjacent to current vertex
list<int>::iterator i;
  for (i = adj[u].begin(); i != adj[u].end(); ++i)
    if (!visited[*i])
      printAllPathsUtil(*i, d, visited, path, path_index);

// Remove current vertex from path[] and mark it as unvisited
visited[u] = false;

So you don't mark B as visited until after you've finished exploring F. And you don't mark F as visited until after you've finished exploring B. So you go back and forth between those two rooms, as if charging down an endless corridor.

Mark B as visited before you explore adjacent rooms.

This got me what I wanted! Thank you so much! – K22 Aug 06 '17 at 22:20 — K22, Aug 06 '17 at 22:20

Infinite loop when trying to find the shortest path in a graph

1 Answers1