# Remember the path in a breadth-first search

This topic is 4437 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 on other sites
Quote:
 Original post by tufflaxThe 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 on other sites
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.

1. 1
2. 2
Rutin
19
3. 3
JoeJ
16
4. 4
5. 5

• 30
• 22
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631700
• Total Posts
3001800
×