你如何使用双向BFS找到最短路径？ 比方说，有一个6x6的网格。 起点是在（0,5）和结束点是在（4,1）。 什么是使用双向BFS的最短路径？ 有没有路径的成本。 它是无方向。
Answer 1:
如何双向BFS工作？
同时运行两个BFS的从源和目标顶点，一旦终止常见的两种运行发现一个顶点。 这个顶点将是半路源和目标之间。
为什么它比BFS更好？
双向BFS将产生比在大多数情况下，简单的BFS更好的结果。 假设源和目标之间的距离为k ，支化因子是B （每个顶点有平均乙边缘）。
- BFS将遍历
1 + B + B^2 + ... + B^k顶点。 - 双向BFS将遍历
2 + 2B^2 + ... + 2B^(k/2)的顶点。
对于大型B和k ，第二个是明显快得多的第一个。
你的情况：
为简单起见，我会认为有在基质中没有任何障碍。 这是发生了什么：
iteration 0 (init):
front1 = { (0,5) }
front2 = { (4,1) }
iteration 1:
front1 = { (0,4), (1,5) }
front2 = { (4,0), (4,2), (3,1), (5,1) }
iteration 2:
front1 = { (0,3), (1,4), (2,5) }
front2 = { (3,0), (5,0), (4,3), (5,2), (3,2), (2,1) }
iteration 3:
front1 = { (0,2), (1,3), (2,4), (3,5) }
front2 = { (2,0), (4,4), (3,3), (5,3), (2,2), (1,1), }
iteration 4:
front1 = { (0,1), (1,2), .... }
front2 = { (1,2) , .... }
现在，我们已经发现，各条战线相交于（1,2），以采取从源和目标顶点到达那里的路径在一起：
path1: (0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2)
path2: (4,1) -> (3,1) -> (2,1) -> (1,1) -> (1,2)
现在，我们只需要反向路径2并追加到路径1（删除课程的共同相交顶点之一），给我们我们的完整路径：
(0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) -> (1,1) -> (2,1) -> (3,1) -> (4,1)
文章来源: How do you use a Bidirectional BFS to find the shortest path?
