Bidirectional BFS Meeting Node

Problem

Find the meeting node of a shortest path with bidirectional BFS.

Expand one level from src, check whether any newly reached node is already known from dst, then expand one level from dst and check again. Return [meeting_node, distance]; when several nodes meet at the minimal distance, pick the smallest node. Return [-1, -1] when the nodes are disconnected. edges is a list of [u, v] pairs.

Hint

Two BFS frontiers meet in the middle, potentially saving half the explored nodes.

Test cases

case 1

in: [6,[[0,1],[1,2],[2,5],[0,3],[3,4],[4,5]],0,5]

expected: [2,3]

case 2

in: [3,[[0,1],[1,2]],0,2]

expected: [1,2]

case 3

in: [3,[[0,1]],0,2]

expected: [-1,-1]

case 4

in: [2,[],0,0]

expected: [0,0]

case 5

in: [4,[[0,1],[1,2],[2,3]],0,3]

expected: [2,3]

Starter codePython

def bidirectional_bfs_meeting(n, edges, src, dst):
    # Your code here
    pass

5 test cases · run your code against them in the editor