ChairMan's blog

By ChairMan, history, 3 years ago, In English

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.

  • Vote: I like it
  • -17
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

Hope i helped ^^