Search code examples
algorithmsearchdata-structuresbidirectional

Can bi-directional searches be used where there are multiple goal nodes?


If I have some sort of data structure that I wish to conduct a search on that has a single starting node but multiple goal nodes, can I still use a bi-directional search algorithm?


Solution

  • Why not? You can think of it in the following manner - add an auxiliary non-existent node that is connected to all the goal nodes with distance zero and then perform bi-directional search between the start node and the new one.

    Of course you don't actually NEED to add this node this was just to illustrate the idea.