Bidirectional BFS

Report a typo

There is a modification of BFS that in some cases allows us to find the shortest path between a source and a target node faster. The idea is to run the procedure simultaneously from the source and the target node. The process continues until the traversals reach the same node vv. This node will be an intermediate node of the shortest path between the source and the target. Intuitively, when we run BFS simultaneously from two nodes, we need to visit fewer nodes compared to the original version because the number of "branches" (neighbors) to be considered during the traversals is likely to be smaller.

Your task here is to apply the modification for the following undirected graph:

Bidirectional BFS

Choose the node BB as a source and the node MM as a target. Apply one step of BFS for the node BB, then one step for the node MM and so on.

As an answer to the problem, print the label of the node where two traversals intersect.

Enter a short text
___

Create a free account to access the full topic