是否有任何双向搜索Dijkstra算法的实现？

Question

我正在寻找Java中Dijkstra(或任何其他源到目的地最短路径算法)的双向搜索(也称为"中间相遇"算法)的实现.

由于双向搜索处理比它看起来更棘手(图算法,第26页),我想在重新发明轮子之前考虑现有的实现!

PS:我说的是双向搜索,不要与双向图混淆)

以下是一个棘手的图表示例:

Answer 1

是的,至少在Java中:https://github.com/coderodde/GraphSearchPal/blob/master/src/main/java/net/coderodde/gsp/model/support/BidirectionalDijkstraPathFinder.java

在双向Dijkstra算法中,您实际上维护了两个"Dijkstra算法":前向搜索和后向搜索.现在,前向搜索类似于单向Dijkstra算法.然而,向后搜索以"反向"方式进行.如果存在有向边(通俗地称为弧)(u, v),则前向搜索将从其遍历u到v,而向后搜索将在相反方向上执行相同操作.

因为两个搜索进程(通常)在源节点和目标节点之间的某个地方相遇,所以我们需要另一个终止条件,这在双向Dijkstra的算法中是

g(top(OPEN_forward)) + g(top(OPEN_backward)) > l

其中l是源节点和目标节点之间迄今为止已知最短路径的长度.

您可能只在双向版本中看到的附加代码是检查每次改进g任何节点的值时缩短最短路径候选的可能性.(g节点的值u是距搜索开始的节点的最短距离(已知到目前为止)u.)