能否修改双向BFS以枚举无权有向图中两节点的所有最短路径？

标准单向BFS可以扩展为输出无权有向图中两顶点间的所有最短路径——不管图是否含环都能实现，已有不少单向BFS枚举所有最短路径的实现思路和代码示例。而双向BFS作为单向BFS的变体，在多数场景下搜索速度更快，但现有主流实现（比如NetworkX中的bidirectional_shortest_path和bidirectional_dijkstra，后者在边权全为1时退化为BFS）仅能返回一条最短路径。由此引出问题：能否修改双向BFS算法，让它也能返回无权有向图中两特定节点间的所有最短路径？

答案是肯定的，只要对双向BFS的核心逻辑做针对性调整，就能实现枚举所有最短路径的功能，具体思路如下：

• 记录完整的路径前驱/后继信息
  正向搜索（从起点出发）时，为每个节点记录所有能以最短距离到达它的前驱节点；反向搜索（从终点出发，遍历反向边）时，为每个节点记录所有能以最短距离到达它的后继节点（即原图中指向它的节点）。只有当新路径的距离等于该节点已知的最短距离时，才将对应的前驱/后继加入记录，避免引入非最短路径的节点。

• 确定交汇节点集合
  当双向搜索过程中，找到所有满足「正向距离 + 反向距离 = 最短路径总长度」的节点，这些节点是正向和反向路径的交汇点。

• 拼接所有路径
  对每个交汇节点，将正向搜索中从起点到该节点的所有最短路径，与反向搜索中从该节点到终点的所有最短路径（注意反转反向路径的顺序，还原为原图中的路径方向）进行组合，得到完整的最短路径。

• 去重（可选）
  如果图中存在环，可能会出现重复路径，需要额外去重；若为无环图，这一步通常可以省略。

这种修改后的双向BFS，既保留了原算法的效率优势（减少遍历节点数），又能完整枚举所有最短路径。NetworkX的现有实现仅返回单条路径，是因为它做了“找到即返回”的优化，并非双向BFS本身无法实现多路径枚举。

内容的提问来源于stack exchange，提问作者user688486