### ChairMan's blog

By ChairMan, history, 19 months ago,

Hi, i'm trying to solve a cool problem but can't figure out how we can do it.

What is the minimum number of $moves$ to get from $x$ to $z$.

Input :

N

X, Y

pairs...

Eg :

5

1 3

1 2

2 4

2 5

5 6

6 3

ANS = 5 : 1,2 — 2,4 — 2,5 — 5,6 — 6,3

if someome please can help me with implementation , it would be cool.

• -17

| Write comment?
 » 19 months ago, # | ← Rev. 3 →   0 the problem is about shortest path from point x to point y, and DFS dont solve shortest path in graphs ( except for trees ), but Why it don't work ? well, depth first search is about going to the deepest point first , so something like this , , and lets say u want shortest path from 1 to 6 , by using dfs , ur path would be like this 1-2-4-5-3 , it's obvious here , that by Depth first search, the distance from 1 to 5 is 3, while it should 2 ! that was a counter-example on why we shouldn't use depth first search on shortest path problems , but how do we fix it ? well , since we really care about the depth of every node , and when i say depth , i mean the distance from the node i start with , to every node , [for example in previous picture , node 1 was in depth 0 , while node 2,3 was in depth 1 ] then we can use Breadth first search , since we move to every child and go along with it, thus we can easily do the depth of every node accurately , while in depth first search, we were going to the depth of the first child , and when we finish it , we go to the second child and so on . Code By BFS#include using namespace std; int BFS(int &start, int &end ,vector>&adj,int &n){ queueq; vectordist(n+2); q.push(start); dist[start]=0; while(!q.empty()){ int father = q.front(); q.pop(); for(auto child : adj[father]){ if(dist[child] == 0 and child != 1){ dist[child]= dist[father] + 1; q.push(child); } } } return dist[end]+1; // because we started with depth 0 } int main(){ int n; cin>>n; int sz = n+3;//make sz equal to the maximum number u can get +1 , example : x,y<=n , then sz =n+1 vector>adj(sz);//because numbers are up to n int start ,end; cin>>start>>end; for(int i = 0 ; i >x>>y; adj[x].push_back(y); adj[y].push_back(x); } cout<