我刚刚阅读了使用双向搜索(在this上)的最短路径的Dijkstra算法的NetworkX实现。该方法的终止点是什么？
最佳答案
我将基于networkx的实现。
双向Dijkstra在两个方向上遇到相同的节点时会停止-但它在该点返回的路径可能不通过该节点。它正在做其他计算以跟踪最短路径的最佳候选者。
我将根据您的评论(根据this answer)作出解释。
供引用，如下图:
当我在反例中在(无向)网络上运行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路径的长度(此声明不一定很明显，但这是此方法的关键)。这样我们就可以停止。我们返回之前找到的候选路径。关于python - NetworkX的“Bidirectional Dijkstra”，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35779969/