NetworkX的"双向Dijkstra"

Question

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

Answer 1

我将基于networkx的实现.

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

我将根据你的评论做出我的解释(在这个答案上)

考虑这个简单的图(包含节点A,B,C,D,E).该图的边缘及其权重为:"A-> B:1","A-> C:6","A-> D:4","A-> E:10","D-> C:3" , "C-> E:1".当我在两侧使用Dijkstra算法时:在向前它在A之后找到B然后在D中,在向后找到E之后的C然后在此点找到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.所以我们有一个候选最短路径ACE,距离为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我们刚刚描述的路径一样大(这种说法不一定是显而易见的,但这是这种方法的关键).所以我们可以停下来.我们返回之前找到的候选路径.