How to get the path between 2 nodes using Breadth-First Search?

Question

I am trying to find a path between two nodes in a graph, where the edges are unweighted.

I am using a Breadth First Search, which stops when it finds the target, in order to find the existence of a path, but I am not sure how to get the path itself.

I tried looking at the list of visited nodes, but this did not seem to help. I saw someone answer this question using prolog, but I am a C++ programmer.

I also looked at Dijkstras algorithm, but this seems like over kill, since a simple Breadth-first Search has got me almost the whole way.

How to get the path between 2 nodes using Breadth-First Search?

score 25 · Accepted Answer · edited Jan 10 '14 at 19:09

25

In your node struct, you add a variable called parentNode which is the parent of that node in the path. In the end, you can retrieve the path by traversing from the goal node backward.

edited Jan 10 '14 at 19:09

Wayne

59,728
15
131
126

answered Mar 01 '11 at 02:48

Thuy

994
8
16

8

I think this approach would work for trees, but not for graphs, where a node might have multiple parents. In this case, we might need to maintain a list as the path is constructed. – Rich Ashworth Nov 04 '14 at 14:59
1

@RichAshworth If you only care about the shortest path, wouldn't it be sufficient to just store the first parent encountered since that will be the quickest way to reach the current node even if you could reach it through other parents? – EnriqueC Apr 05 '20 at 19:58
What if without having to resort to new vars? – lkahtz Aug 04 '20 at 12:49

score 2 · Answer 2 · edited Oct 12 '20 at 03:25

I found this simple algorithm which stores the path to the node along with the node in the queue here: https://stackoverflow.com/a/50575971/5883177 So when we pop a node from the queue, we also get the path to that node readily.

The code in the link is in python which uses tuples to store the pair. Here is a C++ implementation of the same which uses std::pair.

bool findPath(Node *n1, Node *n2, vector<Node*> &path)
{
    // We use queue to perform a BFS traversal and in addition to storing the
    // node we'll also store the path so far to the node.
    queue<pair<Node*,vector<Node*>>> q;
    
    // Visit the first node and add it to the queue.
    n1->visited=1;
    // Form the path, create a pair and add it the queue.
    vector<Node*> p;
    p.push_back(n1);
    q.push(make_pair(n1,p));
    
    while(!q.empty())
    {
        pair<Node*,vector<Node*>> curPair = q.front();
        q.pop();
        
        // visit all the unvisited nodes and check if there is n2 in it.
        for(Node *u : curPair.first->adjNodes ){
            if(u->visited == 0){
                
                if(u->value == n2->value){
                    // found our destination. Return true
                    // form the path by appending this node to the path till now
                    curPair.second.push_back(u);
                    // update the passed 'path' vector with the path so far.
                    path = curPair.second; // all nodes will be copied into path
                    return true;
                }
                
                // Not our node, visit the node if unvisited
                if(u->visited == 0){
                    u->visited = 1;
                    // Create a new path with this node added.
                    // Path so far can be obtained from the pair in queue
                    vector<Node*> newPath(curPair.second);
                    newPath.push_back(u);
                    // Add the node and the path to it into the queue.
                    q.push(make_pair(u, newPath));
                }
            }
        }
    }
    
    return false;
}


class Node{
    public:
    Node(int val) 
    { 
        value = val; 
        visited=0; 
    }
        
    int value;
    vector<Node*> adjNodes;
    int visited;
};

How to get the path between 2 nodes using Breadth-First Search?

2 Answers2

Linked