How to quickly find the shortest path in the first search?
I'm using the first breadth-first search to find a location in a graph and I'm sure my algorithm is working correctly, but I'm worried about 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 plot the shortest path from end to start. Any help would be appreciated.
Thank.
source to share
One of the options would be as follows. Create a way to map each node to a "parent" node (perhaps a hash table, or perhaps adding a "parent" field to whatever type represents the node). Then, whenever you unload node u from the queue and are about to add node v to the queue, set v's parent pointer to be node u. This means that the way you got to node v is to path to u and then expand the path one edge to go to v.
Once you have done that and finished your BFS, you can read the shortest path backward reference starting at the destination node and then re-following the parent's pointer until you return to the beginning of the node. After that, you can simply undo that path to get the shortest path back.
Hope this helps!
source to share