“双向迪杰斯特拉"由 NetworkX [英] "Bidirectional Dijkstra" by NetworkX
问题描述
我刚刚阅读了使用双向搜索的最短路径 Dijkstra 算法的 NetworkX 实现(在
当我在反例中的(无向)网络上运行 networkx 的双向 dijkstra 时，您声称该评论:"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
{} {}它会在每个周围建立集群".它首先将 A 放入与 A
{A:0} {}现在它检查 A 是否已经在 E 周围的集群中(当前为空).它不是.接下来，它查看 A 的每个邻居，并检查它们是否在 E 周围的集群中.他们不是.然后将所有这些邻居放入一个由 A 的路径长度排序的 A 即将到来的邻居的堆(就像一个有序列表).称其为 A
clusters ..... 条纹{A:0} {} ..... A:[(B,1), (D,4), (C,6), (E,10)]电子:[]现在检查E.对于 E 它做对称的事情.将 E 放入其簇中.检查E 是否不在A 周围的簇中.然后检查它的所有邻居，看看是否有任何在 A 周围的集群中(它们不是).然后创建E的边缘.
簇状条纹{A:0} {E:0} ..... A:[(B,1), (D,4), (C,6), (E,10)]E:[(C,1), (A,10)]现在回到A.它从列表中取出 B 并将其添加到围绕 A 的集群中.它检查 B 的任何邻居是否在 E 周围的集群中(没有邻居要考虑).所以我们有:
簇状条纹{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).我们有:
簇状条纹{A:0, B:1} {E:0, C:1} ..... A:[(D,4), (C,6), (E,10)]E:[(D,4), (A,10)]候选路径:A-C-E，长度 7回到A:我们从它的边缘得到下一个东西，D.我们把它加入到A的簇中，注意它的邻居C在E的簇中.所以我们有一个新的候选路径，A-D-C-E，但它的长度大于 7，所以我们将其丢弃.
簇状条纹{A:0, B:1, D:4} {E:0, C:1} ..... A:[(C,6), (E,10)]E:[(D,4), (A,10)]候选路径:A-C-E，长度 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.
这篇关于“双向迪杰斯特拉"由 NetworkX的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
