Блог пользователя ChairMan

Автор ChairMan, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
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

Hope i helped ^^