How to find the distance between two nodes using BFS?

Question

I wrote this code of BFS in c++ using wikipedia's pseudocode. The function takes two parameters s,t. Where s is the source node and t is the target, if the target is fount, the the search return the target itself, or else it return -1. Here is my code:

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

struct vertex{
vector<int> edges;
bool visited;
};

int dist = 0;

int BFS(vertex Graph[],int v,int target){
deque<int> Q;
Q.push_front(v);
Graph[v].visited = true;
    while(!Q.empty()){
        int t = Q.back();
        Q.pop_back();
            if(t == target){
                return t;
            }
            for(unsigned int i = 0;i < Graph[t].edges.size();i++){
                int u = Graph[t].edges[i];
                if(!Graph[u].visited){
                    Graph[u].visited = true;
                    Q.push_front(u);
                }
            }
    }
    return -1;
} 

int main(){
int n;
cin >> n;
vertex Graph[n];
int k;
cin >> k;
for(int i = 0;i < k; i++){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    Graph[a].edges.push_back(b);
    Graph[b].edges.push_back(a);
}

for(int i = 0;i < n; i++){
    Graph[i].visited = false;
}

int s,t;
cin >> s >> t;

cout << BFS(Graph,s,t);

  }

I read this in wikipedia :

Breadth-first search can be used to solve many problems in graph theory, for example:
Finding the shortest path between two nodes u and v (with path length measured by number > > of edges)

How do i change my function BFS to return the shortest path from s to t and return -1 if no path exists?

Hyatt

create a variable for storing distance from starting node. everytime when you travel to a new node, update this distance variable. – Peruse

@PaulDinh but will this give the shortest distance, or only the distance? – Hyatt

as your implementation above, if putting a distance variable in, it is only the distance to current node when travelling. – Peruse

@PaulDinh i did it just like you said, but when update the distance variable every time i travel to a new node, the answer is much greater than the actual answer. – Hyatt

Answer 1

When you generate a new node, keep track of the id of the parent that generated the node. Then, when you reach the goal, you just trace the parents backwards until you reach the start state. You can, for instance, mark the start as its own parent, which means that it is the start state. Or, just use a pre-defined value (-1) to say there is no parent.

So, in your code, instead of marking a state as visited, have a parent id. Parent ids can be set to -1 initially, and then updated when they are changed. The parent id can just the location in the graph structure of the parent.

Continuous

Answer 2

Breadth-first search, by definition, visits all nodes at distance d from the starting point before visiting any nodes at distance d+1. So when you traverse the graph in breadth-first order, the first time you encounter the target node, you've gotten there by the shortest possible route.

Nathan S.' answer is correct, though I hope this answer provides some more intuition about why this works. Paul Dinh's comment is also correct; you can modify Nathan's answer to track distance instead of the actual path pretty trivially.

Agnosia

can you please tell at exactly which point in the code should i increment the counter? – Hyatt

That is a tricky piece, yes! When you pop a node off the deque, you'll get the distance to that node as well. Each neighbor you then push onto the deque has its parent's distance plus 1. – Agnosia

So should i maintain a seperate variable for each vertex, to store the distance from its parent? – Hyatt

Yes, the straightforward way of implementing this needs storage proportional to the number of nodes you visit. But, some questions you should consider: 1) Are you already allocating structures that you can add this data to? 2) Do you want to remember these distances for all nodes, or free the memory after you've found your target? (That depends on your application.) 3) How could you change the algorithm to measure shortest distance using only one variable for the current depth? – Agnosia

Answer 3

For a good implementation and explanation of the BFS algorithm checkout this ( CXXGraph ) library source code.

Synagogue

This should be a comment, not an answer. – Bulletin

First of all, there is no explanation for the BFS algorithm in your link. Secondly, this doesn't answer the question and third, are you plugging your own GitHub?? – Livia