When should us use normal BFS over bidirectional BFS?

user_5946480 0
Viewed 143

I understand that Bidirectional BFS has a lot of advantage over using normal BFS, as it theoretically halves the time to discover the shortest path between two nodes and the time to find if a node is reachable from another node.

Also I understand that we should use Bidirectional only if we have Uniquely defined both the nodes.

Is there any situation when we should prefer a normal BFS over bidirectional BFS?

breadth-first-search graph-theory graph time-complexity algorithm
1 Answers

I understand that bidirectional BFS consists of, given start and goal nodes, alternately expanding layers of nodes from start and goal, until a node in the middle has been reached from both ends. The shortest path from start to goal is then understood to be the shortest from start to middle node, continued by the shortest from middle to goal. I can see that less nodes may need to be expanded as compared with a standard BFS approach. However,

  • It is easier to implement standard BFS (sBFS) than to implement a bidirectional BFS (bBFS for short). Simple is often good, as it is easier to code and to later verify its correctness.
  • If the graph is directed and unweighted, sBFS guarantees that it will find the shortest path from start to goal in minimal steps; bBFS is not guaranteed to work with directed graphs.
  • After running sBFS, you can reconstruct shortest paths from the start to all nodes that are at most 1 step before the goal node (that is, before the search was stopped). This may be valuable in and of itself. Running bBFS does not generate such a list.

With this in mind, I would argue the bBFS is only useful for a very narrow case (where, depending on the graph, it is expected to perform better than sBFS), and sBFS is both simpler and useful in a larger range of scenarios.

user_154720
Related