java - Dijkstra算法有双向搜索的实现吗？

Question

我正在为 Java 中的 Dijkstra（或任何其他源到目的地最短路径算法）寻找双向搜索（又名“在中间相遇”算法）的实现。

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

PS：我说的是双向搜索，不要与双向图混淆）

这是一个棘手的图表示例：

Answer 1

Yes, there is at least in Java: https://github.com/coderodde/GraphSearchPal/blob/master/src/main/java/net/coderodde/gsp/model/support/BidirectionalDijkstraPathFinder.java

In a bidirectional Dijkstra's algorithm, you maintain actually two "Dijkstra's algorithms": the forward search and the backward search. Now, the forward search resembles a lot the unidirectional Dijkstra's algorithm. The backward search, however, proceeds in "reversed" fashion. If there is a directed edge (colloquially called an arc) (u, v), the forward search would traverse it from u to v, whereas the backward search would do the same in opposite direction.

Because the two search processes meet (usually) somewhere in between the source node and the target node, we need another termination condition, which in bidirectional Dijkstra's algorithm is

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

where l is the length of the shortest known so far path between the source and target nodes.

Additional code you might see only in bidirectional version is checking the possibility of shortening a shortest path candidate every time you improve the g value of any node. (The g value of a node u is the shortest (known so far) distance from the node from which the search started to u.)