How to reconstruct paths using BFS

Question

I've learned that Breadth-First Search is an algorithm that can be used to calculate the shortest distance between two nodes. I have implemented a BFS algorithm in the code below:

#define N 4 
#define M 4 

// QItem for current location and distance 
// from source location 
class QItem {
public:
    int row;
    int col;
    int dist;
    QItem(int x, int y, int w)
        : row(x), col(y), dist(w)
    {
    }
};


int minDistance(char grid[N][M])
{
    QItem source(0, 0, 0);

    // To keep track of visited QItems. Marking 
    // blocked cells as visited. 
    bool visited[N][M];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
        {
            if (grid[i][j] == '0')
                visited[i][j] = true;
            else
                visited[i][j] = false;

            // Finding source 
            if (grid[i][j] == 's')
            {
                source.row = i;
                source.col = j;
            }
        }
    }

    // applying BFS on matrix cells starting from source 
    queue<QItem> q;
    q.push(source);
    visited[source.row][source.col] = true;
    while (!q.empty()) {
        QItem p = q.front();
        q.pop();

        if (grid[p.row][p.col] == 'd')
            return p.dist;

        if (p.row - 1 >= 0 && visited[p.row - 1][p.col] == false) {
            q.push(QItem(p.row - 1, p.col, p.dist + 1));
            visited[p.row - 1][p.col] = true;
        }

        if (p.row + 1 < N && visited[p.row + 1][p.col] == false) {
            q.push(QItem(p.row + 1, p.col, p.dist + 1));
            visited[p.row + 1][p.col] = true;
        }

        if (p.col - 1 >= 0 && visited[p.row][p.col - 1] == false) {
            q.push(QItem(p.row, p.col - 1, p.dist + 1));
            visited[p.row][p.col - 1] = true;
        }

        if (p.col + 1 < M && visited[p.row][p.col + 1] == false) {
            q.push(QItem(p.row, p.col + 1, p.dist + 1));
            visited[p.row][p.col + 1] = true;
        }
    }
    return -1;
}

int main()
{
    char grid[N][M] = { { '0', '*', '0', 's' },
                        { '*', '0', '*', '*' },
                        { '0', '*', '*', '*' },
                        { 'd', '*', '*', '*' } };

    cout << minDistance(grid);
    return 0;
}

My question is, does there exist an efficient way to reconstruct a path between two nodes without running another algorithm? If not, is there another shortest-path algorithm that can reconstruct paths?

See here (duplicate): https://stackoverflow.com/questions/8922060/how-to-trace-the-path-in-a-breadth-first-search — Yannic, Jul 08 '20 at 20:49
I've already seen that but I was not able to fix that like this in my code — itranger, Jul 08 '20 at 20:53
It would be useful if you include why that solution doesn't work. — elersong, Jul 08 '20 at 21:20
I only understand that I need a parent of that node in the path that I can retrieve the path by traversing from the goal node backward - But how can I add this to my code without running another algorithm? — itranger, Jul 09 '20 at 06:46

Telescope · Answer 1 · 2020-07-08T21:08:46.733

To reconstruct paths with breadth-first search, you can keep a parent vector that keeps track of each node's parent. After the BFS finishes running, you can trace backwards from the end node back to the beginning to construct your path.

Here's some code which illustrates this:

while(!Q.empty){
    int curr = Q.front();
    Q.pop();

    if(curr == destination){break;}

    for(int item : adj[curr]){ // for every element adjacent to curr
        if(!visited[item]){
            visited[item] = true;
            parent[item] = curr; // connects curr to item
            Q.push(item);
        }
    }
}

// trace from the destination back to the start
int tracer = destination;
vector <int> path = {tracer};

while(tracer != start){
    tracer = parent[tracer];
    path.push_back(tracer);
}

// note that this constructs path in reverse order (from end to start)

In your case, parent should be a map <QItem, QItem>, keeping track of each QItem's parent.

How to reconstruct paths using BFS

1 Answers1