Dijkstra的双向实现

Question

我正在实现一个双向Dijkstra算法，但是我不理解各种停止条件的实现方式。以这个图为例，我们从节点A开始，目标是节点J。下面列出了算法停止时已处理的簇(cluster)和松弛(relaxed)的节点:

NetworkX的“Bidirectional Dijkstra”所接受的答案解释说，当同一节点在两个方向上都被处理时，算法就会停止。在我的图中，这将是节点F。如果是这样，算法在找到长度为9的最短路径A-B-C...H-I-J后停止。但这不是最短路径，因为A-J之间有一条长度为8的直接边，它永远不会被取出，因为权重8从未从优先队列中弹出。

即使在这个Java实现中，coderodde的Github代码中，Dijkstra的双向算法的停止条件也是：

double mtmp = DISTANCEA.get(OPENA.min()) +
                          DISTANCEB.get(OPENB.min());            
if (mtmp >= bestPathLength) return PATH;

这个算法会在前向队列和后向队列中顶部节点的权值之和至少达到目前为止的最佳路径长度时停止。但这并不能返回正确的最短路径。因为在这种情况下，节点G（6）和E（5）的权值总和为11，这比目前为止的长度为9的最佳路径更长。

我不明白这两个看似都是停止条件的方法都会得出错误的最短路径。我不确定我哪里理解有误。

Dijkstra双向算法的一个好的停止条件是什么？此外，双向A*的停止条件是什么？

- rahulg510

Answer 1

从概念上讲，Dijkstra算法的停止条件，无论是双向还是单向，都是在找到的最佳路径与您继续寻找可能找到的任何路径一样好时停止。只有封闭路径（上面的“簇”集合中的路径）才算作已找到的路径。

对于双向Dijkstra算法，只要前向和后向封闭集合中存在相同的顶点，就认为已“找到”一条路径。这部分很容易，但未来可能找到的最佳路径有多好呢？

为确保您获得的答案是正确的，您对可能找到的最佳路径的评估需要准确或低估。让我们考虑以下情况：

1. 可能使用一个在两个方向上都是开放的顶点构建路径。 2. 在一个方向上开放的顶点可能与在另一个方向上已关闭的顶点构成路径。

问题在于情况（2）。我们用于Dijkstra算法的集合和优先队列不能在这种情况下提供非常有用的最佳路径低估。封闭集合中的最小距离始终为0，如果将此添加到另一个方向的最小开放距离中，则得出：

double mtmp = min ( DISTANCEA.get(OPENA.min()) , DISTANCEB.get(OPENB.min()) );

这个方法确实可以得出正确的答案，但是它会让算法在至少一个方向上运行直到找到最佳完整路径。在许多情况下，单向Dijkstra算法会更快。

我认为这个“双向Dijkstra算法”的想法需要进行重大改进才能变得真正好用。

- Matt Timmermans