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

Автор aman_naughty, история, 5 лет назад, По-английски

Hi, I was going through this point of bfs application from cpalgorithms,

Find the shortest path of even length from a source vertex s to a target vertex t in an unweighted graph: For this, we must construct an auxiliary graph, whose vertices are the state (v,c), where v — the current node, c=0 or c=1 — the current parity. Any edge (a,b) of the original graph in this new column will turn into two edges ((u,0),(v,1)) and ((u,1),(v,0)). After that we run a BFS to find the shortest path from the starting vertex (s,0) to the end vertex (t,0).

I was wondering if this problem can be solved as follows:

Run bfs from src and store the shortest distance from src in an array a.
Run bfs from dest and store the shortest distance from dest in an array b.
Now iterate over all the vertices u and check if a[u]+b[u] is even and if so then get the minimum distance.
Is this approach correct or am I thinking wrong.
  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Try this graph:
5 nodes from 0 to 4
with 6 edges:
0 1
0 2
1 3
2 3
2 4
3 4
src = 0 and dst = 2
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Wow thanks for the test case. My approach is indeed wrong and their approach is correct.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      i don't understand the approach which is mentioned above, will u pls tell me??

      thanks in advancce