aman_naughty's blog

Help needed in bfs problem ?
By aman_naughty, history, 5 years ago, In English

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.
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it 
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
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      thanks in advancce

      → Reply