Sign in to follow this  
tufflax

Remember the path in a breadth-first search

Recommended Posts

Hey! I have a problem. It goes like this: I have a graph and I need to find my way from one vertex to another, the shortest way. So, I do a breadth-first search. Fine. But I need to remember how I got there, which edges I walked on. I can do it in O(|V|) (linear with respect to the number of vertices) time but I need it to be faster. The fastest one can hope for is probably linear with respect to the number of edges in the path. Hm, interesting... :)

Share this post


Link to post
Share on other sites
For each vertex you encounter while searching, store a pointer to the vertex from which you arrived at the current vertex. When you reach the target, simply follow these "parent" pointers back to the beginning. That is your path.

Also remember that if you can make some assumptions about the graph (eg. if you can assign a cost/distance metric to the edges), there exist much quicker search algorithms than a naive breath-first search.

Share this post


Link to post
Share on other sites
Quote:
Original post by tufflax
The fastest one can hope for is probably linear with respect to the number of edges in the path.


Uh, in the worst case, O(|E|) == O(|V|^2).

You're doing just fine.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Do what Sharlin said and search the path from finish to start. That way you don't have to reverse the path vertecies to get the correct order. If order matters to you that is.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this