是否有任何双向搜索Dijkstra算法的实现？
我正在寻找Java中Dijkstra（或任何其他源到目的地最短路径算法）的双向搜索（也称为“中间相遇”算法）的实现。
由于双向搜索处理比它看起来更棘手（ 图算法，第26页 ），我想在重新发明轮子之前考虑现有的实现！
PS：我说的是双向搜索 ，不要与双向图混淆）
这是一个棘手的图表示例：
是的，至少在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值时缩短最短路径候选的可能性。 （节点u的g值是从搜索开始的节点开始到u的最短（已知）距离。）