"Bidirectional Dijkstra" 来自 NetworkX

Question

我刚刚阅读了使用双向搜索的最短路径 Dijkstra 算法的 NetworkX 实现（在 this）。这个方法的终点是什么？

Answer 1

我将以 networkx 的实现为基础。

双向 Dijkstra 在两个方向遇到同一个节点时停止 - 但它 return 在该点的路径可能不通过该节点。它正在进行额外的计算以跟踪最短路径的最佳候选者。

我将根据您的评论（在 this answer 上）进行解释

Consider this simple graph (with nodes A,B,C,D,E). The edges of this graph and their weights are: "A->B:1","A->C:6","A->D:4","A->E:10","D->C:3","C->E:1". when I use Dijkstra algorithm for this graph in both sides: in forward it finds B after A and then D, in backward it finds C after E and then D. in this point, both sets have same vertex and an intersection. Does this is the termination point or It must be continued? because this answer (A->D->C->E) is incorrect.

供参考，下面是图表：

当我运行在反例中的（无向）网络上使用 networkx 的双向 dijkstra 时，您声称评论："A->B:1","A->C:6","A->D:4","A->E:10","D->C:3","C->E:1"：它给了我：(7, ['A', 'C', 'E'])，而不是 A-D-C-E.

问题是在它停止之前误解了它在做什么。它在查找节点方面完全符合您的预期，但在执行此操作时，会进行额外的处理以找到最短路径。当它从两个方向到达 D 时，它已经收集了其他一些可能更短的 "candidate" 路径。不能保证仅仅因为节点 D 从两个方向到达最终成为最短路径的一部分。相反，在从两个方向到达节点时，当前候选最短路径比它继续运行ning.

时会找到的任何候选路径都短。

算法从两个空簇开始，每个簇与 A 或 E

相关联

{}          {}

它会在每个周围建立 "clusters"。它首先将 A 放入与 A

关联的集群中

{A:0}          {}

现在它检查 A 是否已经在 E 周围的集群中（当前为空）。它不是。接下来，它查看 A 的每个邻居并检查它们是否在 E 周围的集群中。他们不是。然后，它会将所有这些邻居放入 A 的即将到来的邻居的堆（如有序列表）中，这些邻居按路径长度从 A 排序。称其为 A

的 'fringe'

clusters                 .....        fringes

{A:0}          {}        .....        A:[(B,1), (D,4), (C,6), (E,10)]
                                      E:[]

现在它检查 E。对于 E 它做对称的事情。将 E 放入其簇中。检查 E 是否不在 A 周围的集群中。然后检查它的所有邻居，看看是否有 A 周围的集群（它们不是）。然后创建 E.

的边缘

clusters                                  fringes
{A:0}          {E:0}        .....        A:[(B,1), (D,4), (C,6), (E,10)]
                                         E:[(C,1), (A,10)]

现在又回到了 A。它从列表中取出 B，并将其添加到 A 周围的集群中。它检查 B 的任何邻居是否在 E 周围的集群中（没有要考虑的邻居）。所以我们有：

clusters                                  fringes
{A:0, B:1}        {E:0}     .....        A:[(D,4), (C,6), (E,10)]
                                         E:[(C,1), (A,10)]

回到E：我们将C添加到E的集群中，并检查C的任何邻居是否在A的集群中.你知道什么，有A。所以我们有一个候选最短路径 A-C-E，距离为 7。我们会坚持下去。我们添加 D 以添加到 E 的边缘（距离为 4，因为它是 1+3）。我们有：

clusters                                  fringes
{A:0, B:1}        {E:0, C:1}     .....   A:[(D,4), (C,6), (E,10)]
                                         E:[(D,4), (A,10)]

candidate path: A-C-E, length 7

回到A：我们从它的边缘得到下一个东西，D。我们将它添加到关于 A 的集群中，并注意到它的邻居 C 在关于 E 的集群中。所以我们有一个新的候选路径，A-D-C-E，但是它的长度大于 7，所以我们丢弃它。

clusters                                  fringes
{A:0, B:1, D:4}     {E:0, C:1}     .....   A:[(C,6), (E,10)]
                                           E:[(D,4), (A,10)]

candidate path: A-C-E, length 7

现在我们回到E。我们看D。它位于 A 周围的集群中。我们可以确定，我们将遇到的任何未来候选路径的长度至少与我们刚刚追踪到的 A-D-C-E 路径一样长（这种说法不一定显而易见，但它是这种方法的关键） .所以我们可以停下来。我们return之前找到的候选路径

"Bidirectional Dijkstra" 来自 NetworkX

"Bidirectional Dijkstra" by NetworkX

python

algorithm

graph

shortest-path

networkx