双向 Dijkstra（或统一成本搜索）算法的停止条件

Question

据我了解，双向 Dijkstra 搜索（具有单一开始和终止状态）的停止条件如下

从一个变量开始 mu = infinity 从起始状态 (s) 和终止状态 (t) 开始搜索当两者相交（要么我们当前正向搜索的节点在反向搜索中，要么相反）在节点w处，则重新计算mu为

mu = distance(s,w) + distance(w,t)

然后检查前两个节点（下一个要检查的节点）的组合距离是否 >= mu，如果是，则终止

if distance(s, top_forward_node) + distance(top_reverse_node, t) >= mu, stop

但是如果我在一个简单的三角形上尝试这个，它会失败。假设我有一个三角形 (a,b,c)，其中 ab = 10，bc = 6 和 ac = 7。开始状态 = a，终止状态 = b。显然，最短距离是 ab = 10。但是正向传递从 a 开始，同时查看 b (10) 和 c (7)，反向传递从 b 开始，查看 a (10) 和 c (6)。由于 c 是成本最低的节点，正向传递查看 c，但由于它不在已经查看过的反向节点中，因此它存储它并移动到反向传递。反向遍历查看 c，发现它在正向遍历查看的节点中，并将 mu 值从无穷大更新为 7 + 6。下一个要查看的节点是 b 和 a，路径成本为 10每个，但是如果我简单地将两个 (10 + 10) 相加，我得到的值为 20，即 >= 7 + 6，因此我的算法错误地以 a-c-b 路径终止。我哪里错了？

forward pass explored nodes = [a(0)]
reverse pass explored nodes = [b(0)]
forward pass frontier nodes = [c(7), b(10)]
reverse pass frontier nodes = [c(6), a(10)]

从前向传递边界节点探索 c(7)。它是在反向传递探索节点吗？不。继续前进

forward pass explored nodes = [a(0), c(7)]
forward pass frontier nodes = [b(10)]

从反向传递边界节点探索 c(6)。它在前向传播探索节点中吗？是的。重新计算 mu

mu = distance(a,c) + distance(c,b) = 6 + 7 = 13
reverse pass explored nodes = [b(0), c(6)]
reverse pass frontier nodes = [a(10)]

检查终止

top_node(forward pass frontier nodes) + top_node(reverse pass frontier nodes) >= mu
10 + 10 > 13?

是的。 Return 路径 a-c-b

参考：幻灯片 10 http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf

这个答案对我没有帮助：Termination Criteria for Bidirectional Search

Answer 1

我知道我错在哪里了。在检查我是否与相反的搜索相交时，我应该检查边界和已探索的节点，而不仅仅是已探索的节点。这样做会得到正确的结果。

双向 Dijkstra（或统一成本搜索）算法的停止条件

Stopping criteria for a bidirectional Dijkstra's (or uniform cost search) algorithm

algorithm

search

dijkstra

bidirectional