Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Help needed in bfs problem ?

Revision en1, by aman_naughty, 2019-08-29 16:25:09

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.
Tags #bfs, #help, approach, #beginner

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English aman_naughty 2019-08-29 16:25:09 989 Initial revision (published)