“双向Dijkstra”由NetworkX [英] "Bidirectional Dijkstra" by NetworkX
问题描述
我刚刚阅读了使用双向搜索的最短路径的Dijkstra算法的NetworkX实现（这个）。这种方法的终止点是什么？
我将基于networkx的实现。 b
$ b双向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算法时：在前面它找到B在A之后，然后D在后面找到C在E之后，然后D.在这一点上，两个集合具有相同的顶点和交点。这是终止点还是必须继续？因为这个答案（A-> D-> C-> E）是不正确的。
作为参考，下面是图： A-> B：1， A-> C：6， A-> d：4， A-> E：10， D-> C：3 ，C-> E：1：它给了我：（7，['A'，'C'，'E']），而不是 ADCE 。
问题在于它误解了它停止。它在搜索节点方面完全符合你的期望，但是当它这样做时，会发生额外的处理以找到最短路径。当它从两个方向到达 D 时，它已经收集了一些可能更短的其他候选路径。不能保证仅仅因为节点 D 从两个方向到达，最终成为最短路径的一部分。相反，在从两个方向到达节点的点上，当前候选最短路径比它继续运行时找到的任何候选路径要短。
算法以两个空群集开始，每个都与 A 或 E $ b $关联b
{} {}
围绕每个聚类。它首先将 A 放入与 A
<$相关联的群集中p $ p $
{A：0} {}
A 已经在 E （当前为空）的集群中。不是这样。接下来，它会查看 A 的每个邻居，并检查它们是否位于 E 周围的集群中。他们不是。然后它把所有这些邻居放入一个由 A A 即将到来的邻居的堆（如有序列表） C>。将此称为 A
集群.... （B，1），（D，4），（C，6），（E，10）] $（$，$） b $ b E：[]
现在它检查 E 。对于 E 它是做对称的事情。将 E 放入其群集中。检查 E 不在 A 周围的集群中。然后检查它的所有邻居，看它们是否在 A （它们不是）的集群中。然后创建 E 边缘。
集群边缘
A：[（B，1），（D，4），（C，6），（E，10）]
E：[（现在它回到 A 。它从列表中取得 B ，并将它添加到 A 周围的集群中。它检查 B 的任何邻居是否位于 E 周围的集群中（没有邻居要考虑）。所以我们有：
pre $ 集群边缘
{A：0，B：1} {E：0} .. A：[（C，6），（E，10）]
E：[ c $ c> 返回 E ：我们添加 C > E 的簇，并检查 C 的任何邻居是否位于 A 。你知道什么，有 A 。因此，我们有一个候选人最短路径A-C-E，距离为7.我们将坚持这一点。我们添加 D 添加到 E 边缘（距离4，因为它是1 + 3）。我们有：
集群条纹
{A：0，B：1} {E：0，C：1 A：[（D，4），（C，6），（E，10）]
E：[（D，4），（A，10）]
候选路径：ACE，长度7
返回 A ：我们从它的边缘得到下一个东西， D 。我们将它添加到集群中，并注意它的邻居 C 位于集群中，大约 A C>ë。所以我们有一个新的候选路径 ADCE ，但它的长度大于7，所以我们放弃它。
<$ p （A，B，B，D，D，D，E） ，（E，10）]
E：[（D，4），（A，10）]
候选路径：ACE，长度7
现在我们回到 E 。我们看看 D 。它位于 A 周围的集群中。我们可以确定，我们遇到的任何未来候选人路径的长度至少与我们刚刚描述的 ADCE 路径一样大（这种说法不一定很明显，但这是这种方法的关键）。所以我们可以停止。我们返回前面找到的候选路径。
I just read the NetworkX implementation of Dijkstra's algorithm for shortest paths using bidirectional search (at this). What is the termination point of this method?
I'm going to base this on networkx's implementation.
Bidirectional Dijkstra stops when it encounters the same node in both directions - but the path it returns at that point might not be through that node. It's doing additional calculations to track the best candidate for the shortest path.
I'm going to base my explanation on your comment (on 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.
For reference, here's the graph:
When I run networkx's bidirectional dijkstra on the (undirected) network in the counterexample you claimed that comment: "A->B:1","A->C:6","A->D:4","A->E:10","D->C:3","C->E:1": it gives me: (7, ['A', 'C', 'E']), not A-D-C-E.
The problem is in a misunderstanding of what it's doing before it stops. It does exactly what you're expecting in terms of finding nodes, but while it's doing that there is additional processing happening to find the shortest path. By the time it reaches D from both directions, it has already collected some other "candidate" paths that may be shorter. There is no guarantee that just because the node D is reached from both directions that ends up being part of the shortest path. Rather, at the point that a node has been reached from both directions, the current candidate shortest path is shorter than any candidate paths it would find if it continued running.
The algorithm starts with two empty clusters, each associated with A or E
{} {}
and it will build up "clusters" around each. It first puts A into the cluster associated with A
{A:0} {}
Now it checks if A is already in the cluster around E (which is currently empty). It is not. Next, it looks at each neighbor of A and checks if they are in the cluster around E. They are not. It then places all of those neighbours into a heap (like an ordered list) of upcoming neighbors of A ordered by pathlength from A. Call this the 'fringe' of A
clusters ..... fringes
{A:0} {} ..... A:[(B,1), (D,4), (C,6), (E,10)]
E:[]
Now it checks E. For E it does the symmetric thing. Place E into its cluster. Check that E is not in the cluster around A. Then check all of its neighbors to see if any are in the cluster around A(they are not). Then creates the fringe of E.
clusters fringes
{A:0} {E:0} ..... A:[(B,1), (D,4), (C,6), (E,10)]
E:[(C,1), (A,10)]
Now it goes back to A. It takes B from the list and adds it to the cluster around A. It checks if any neighbor of B is in the cluster around E (there are no neighbors to consider). So we have:
clusters fringes
{A:0, B:1} {E:0} ..... A:[(D,4), (C,6), (E,10)]
E:[(C,1), (A,10)]
Back to E: we add C tot he cluster of E and check whether any neighbor of C is in the cluster of A. What do you know, there's A. So we have a candidate shortest path A-C-E, with distance 7. We'll hold on to that. We add D to add to fringe of E (with distance 4, since it's 1+3). We have:
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
Back to A: We get the next thing from its fringe, D. We add it to the cluster about A, and note that its neighbor C is in the cluster about E. So we have a new candidate path, A-D-C-E, but it's length is greater than 7 so we discard it.
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
Now we go back to E. We look at D. It's in the cluster around A. We can be sure that any future candidate path we would encounter will have length at least as large as the A-D-C-E path we have just traced out (this claim isn't necessarily obvious, but it is the key to this approach). So we can stop. We return the candidate path found earlier.
这篇关于“双向Dijkstra”由NetworkX的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
![A-> B：1， A-> C：6， A-> d：4， A-> E：10， D-> C：3 ，C-> E：1：它给了我：（7，['A'，'C'，'E']），而不是 ADCE 。](https://i.stack.imgur.com/w7aw2.png){kind=link}