python - "Bidirectional Dijkstra"来自 NetworkX

Question

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

Answer 1

我将基于 networkx 的实现。

双向 Dijkstra 在两个方向遇到同一个节点时停止——但它在那个点返回的路径可能不是通过那个节点。它正在做额外的计算来跟踪最短路径的最佳候选者。

我将根据您的评论(在 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 时，它已经收集了一些其他可能更短的“候选”路径。不能保证仅仅因为节点 D 从两个方向到达，最终成为最短路径的一部分。相反，在从两个方向都到达节点时，当前候选最短路径比它继续运行时会找到的任何候选路径都短。

该算法从两个空簇开始，每个簇与 A 或 E 相关联

{}          {}

它将围绕每个建立“集群”。它首先将 A 放入与 A 关联的集群中

{A:0}          {}

现在它检查 A 是否已经在 E 附近的集群中(当前为空)。它不是。接下来，它查看 A 的每个邻居，并检查它们是否在 E 附近的集群中。他们不是。然后它将所有这些邻居放入一个堆(如有序列表)中的 A 即将到来的邻居，按路径长度从 A 排序。将此称为 A 的“边缘”

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 附近的集群中。我们可以确定，我们将遇到的任何 future 候选路径的长度至少与我们刚刚追踪的 A-D-C-E 路径一样大(这种说法不一定很明显，但它是这种方法的关键)。所以我们可以停下来。我们返回之前找到的候选路径。