是否有任何双向搜索Dijkstra算法的实现？ [英] Is there any implementation of bidirectional search for Dijkstra algorithm?

问题描述

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

由于双向搜索处理比看起来更棘手（

在双向Dijkstra算法中，您实际上维护了两个Dijkstra算法：前向搜索和后向搜索。现在，前向搜索类似于单向Dijkstra算法。然而，向后搜索以反向方式进行。如果存在有向边（通俗地称为弧） （u，v） ，则前向搜索将遍历它从 u 到 v ，而向后搜索我会在相反的方向上做同样的事情。

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

  g（顶部（OPEN_forward））+ g（顶部（OPEN_backward））> l 
  

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

您可能只在双向版本中看到的其他代码正在检查缩短a的可能性最短路径候选每时间，您可以改善任何节点的 g 值。 （节点 u 的 g 值是从搜索开始的节点到 u 的最短距离（已知到目前为止）。）

I am looking for an implementation of bidirectional search (a.k.a. "meet in the middle" algorithm) for Dijkstra (or any other source-to-destination shortest path algorithm) in Java.

As bidirectional search processing is trickier than it looks like (Graph Algorithms, p.26), I want to consider an existing implementation before reinventing the wheel!

P.S.: I am talking about bidirectional search, not to be confused with a bidirectional graph)

Here is an example of a tricky graph:

解决方案

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.)

这篇关于是否有任何双向搜索Dijkstra算法的实现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！