我们不能在未加权图中找到DFS（修改的DFS）的最短路径吗？如果没有，那为什么呢？ [英] Can't we find Shortest Path by DFS(Modified DFS) in an unweighted Graph? and if not then Why?

问题描述

据说DFS不能用于在未加权图中找到最短路径。我已经看过多个帖子和博客，但由于对DFS进行一些修改可以使之成为可能，所以不满意。

我认为，如果我们以这种方式使用经过修改的DFS，那么我们可以找到距源的最短距离。

1. 初始化从根到距离的数组，其中无穷大且距离为


2. 遍历时，我们一直跟踪否。的边缘。向前移动时，编号边的数量，而后退轨道的减量的边缘。然后每次检查if（dist（v）> dist（u）+ 1），然后dist（v）= dist（u）+ 1。

通过这种方式，我们可以使用DFS找到距根的最短距离。这样，我们就可以在O（V + E）中找到它，而不是Dijkstra的O（ElogV）。

如果我在某些时候错了。请告诉我。

解决方案

是的，如果以您提到的方式修改了DFS算法，则可以将其用于查找从未加权图中的根开始的最短路径。问题在于，在修改算法时，您已经从根本上改变了算法。

在表面上看起来很小的更改似乎比我夸大了，但它所做的更改超过了您可能会想。

考虑一个图，该图的 n 个节点的编号为 1 到 n 。让每个 k 和 k + 1 之间有一条优势。另外，让 1 连接到每个节点。

由于DFS可以任意顺序选择相邻邻居，因此我们也

现在尝试在您的头部或根目录为 1 。
首先，算法将使用之间的边沿，在 n-1 步骤中达到 n 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用于最短距离计算。

It is said that DFS can't be used to find the shortest path in the unweighted graph. I have read multiple post and blogs but not get satisfied as a little modification in DFS can make it possible.

I think if we use Modified DFS in this way, then we can find the shortest distances from the source.

1. Initialise a array of distances from root with infinity and distance of root from itself as 0.
2. 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.

In this way we can find the shortest distances from the root using DFS. And in this way, we can find it in O(V+E) instead of O(ElogV) by Dijkstra.

If I am wrong at some point. Please tell me.

解决方案

Yes, if the DFS algorithm is modified in the way you mentioned, it can be used to find the shortest paths from a root in an unweighted graph. The problem is that in modifying the algorithm you have fundamentally changed what it is.

It may seem like I am exaggerating as the change looks minor superficially but it changes it more than you might think.

Consider a graph with n nodes numbered 1 to n. Let there be an edge between each k and k + 1. Also, let 1 be connected to every node.

Since DFS can pick adjacent neighbors in any order, let's also assume that this algorithm always picks them in increasing numerical order.

Now try running algorithm in your head or your computer with root 1. First the algorithm will reach n in n-1 steps using edges between 1-2, 2-3 and so on. Then after backtracking, the algorithm moves on to the second neighbor of 1, namely 3. This time there will be n-2 steps. The same process will repeat until the algorithm finally sees 1-n. The algorithm will need O(n ^ 2) rather than O(n) steps to finish. Remember that V = n & E = 2 * n - 3. So it is not O(V + E).

Actually, the algorithm you have described will always finish in O(V^2) on unweighted graphs. I will leave the proof of this claim as an exercise for the reader.

O(V^2) is not that bad. Especially if a graph is dense. But since BFS already provides an answer in O(V + E), nobody uses DFS for shortest distance calculation.

这篇关于我们不能在未加权图中找到DFS（修改的DFS）的最短路径吗？如果没有，那为什么呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！