How do you find the shortest path quickly in a breadth first search?

Question

I'm using breadth first search to find a location in a graph, and I'm pretty sure my algorithm works correctly, but I'm having troubling finding the shortest path to the result when I'm done. Essentially, I can get from my start location to my end location using BFS, but I don't know how to construct the shortest path from the end to the beginning. Any help would be appreciated.

Thank you.

Answer 1

One option would be the following. Create some sort of way of associating each node with a "parent" node (perhaps a hash table, or perhaps by adding a "parent" field to whatever type represents a node). Then, whenever you dequeue a node u from the queue and are about to add a node v into the queue, set v's parent pointer to be the node u. This marks that the way you got to node v was by following the path to u, then extending the path by one edge to get to v.

Once you've done this and finished your BFS, you can read off the reverse of the shortest path by starting with the destination node, then repeatedly following the parent pointer until you arrive back at the start node. Once you have this, you can just reverse this path to get back the actual shortest path.

Hope this helps!