据说在未加权的图中不能用DFS求最短路径。我已阅读多篇文章和博客,但并不满意,因为对 DFS 稍加修改就可以实现。
我认为如果我们以这种方式使用改进的 DFS,那么我们可以找到距源的最短距离。
- Initialise a array of distances from root with infinity and distance of root from itself as 0.
- While traversing, we keep track of no. of edges. On moving forward increment no. of edges and while back track decrement no. of edges. And each time check if(dist(v) > dist(u) + 1 ) then dist(v) = dist(u) + 1.
通过这种方式,我们可以使用 DFS 找到距根的最短距离。通过这种方式,我们可以在 O(V+E) 而不是 Dijkstra 的 O(ElogV) 中找到它。
如果我在某个时候错了。请告诉我。
最佳答案
是的,如果按照您提到的方式修改 DFS 算法,它可以用于在未加权的图中从根找到最短路径。问题在于,在修改算法时,您从根本上改变了它的本质。
这似乎是我在夸大其词,因为表面上看变化很小,但它的变化比您想象的要大。
考虑一个图,其中 n
个节点编号为 1
到 n
。让每个 k
和 k + 1
之间有一条边。此外,让 1
连接到每个节点。
由于 DFS 可以按任何顺序选择相邻的邻居,我们还假设该算法总是按递增的数字顺序选择它们。
现在尝试在您的头脑中或您的计算机中使用根 1
运行算法。
首先,算法将使用 1-2
、2-3
和很快。然后在回溯之后,算法移动到 1
的第二个邻居,即 3
。这次会有n-2
步。
相同的过程将重复,直到算法最终看到 1-n
。
该算法将需要 O(n ^ 2) 而不是 O(n) 步来完成。请记住 V = n & E = 2 * n - 3
。所以它不是 O(V + E)。
实际上,您所描述的算法在未加权图上总是以 O(V^2) 完成。我将把这个主张的证明作为练习留给读者。
O(V^2) 还不错。特别是如果图形是密集的。但是由于 BFS 已经在 O(V + E) 中提供了答案,因此没有人使用 DFS 进行最短距离计算。
关于algorithm - 我们不能在未加权的图中通过 DFS(改进的 DFS)找到最短路径吗?如果不是,那为什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54198910/