NetworkX的“Bidirectional Dijkstra”

Question

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

Answer 1

我将基于networkx的实现。

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

我要立足于您的评论我的解释（上this answer）

考虑一个简单的图形（与节点A，B，C，d，E）。该图的边缘及其权重为：“A-> B：1”，“A-> C：6”，“A-> D：4”，“A-> E：10”，“D-> C：3" ， “C-> E：1”。当我在这个图的两边使用Dijkstra算法时：在前面它找到B在A之后，然后D在后面找到C在E之后，然后D.在这一点上，两个集合具有相同的顶点和交点。这是终止点还是必须继续？因为这个答案（A-> D-> C-> E）不正确。

仅供参考，这里的图：

当我运行在反的（非定向）网络上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附近的群集中。我们可以肯定的是，我们将遇到的任何未来候选人路径的长度至少与我们刚刚查明的A-D-C-E路径一样大（这种说法不一定很明显，但它是这种方法的关键）。所以我们可以停止。我们返回前面找到的候选路径。