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.
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 .
}
Hope i helped ^^