我们不能在未加权的图中通过 DFS（改进的 DFS）找到最短路径吗？如果不是，那为什么？

Question

据说在未加权的图中不能用DFS求最短路径。我已经阅读了多个 post 和博客，但并不满意，因为在 DFS 中稍加修改就可以实现。

我想如果我们这样使用Modified 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) 中找到它。

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

Answer 1

定义图上深度优先搜索的方式，它只访问每个节点一次。当它遇到之前访问过的节点时，它会回溯。

因此，假设您有一个包含节点 A、B、C 的三角形，并且您想要找到从 A 到 B 的最短路径。DFS 遍历的一种可能性是 A -> C -> B，您就完成了。然而，这不是最短路径。

Answer 2

是的，如果按照您提到的方式修改 DFS 算法，它可以用于在未加权的图中从根找到最短路径。问题是在修改算法时你从根本上改变了它的本质。

我似乎在夸大其词，因为从表面上看变化很小，但它的变化比您想象的要大。

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

由于 DFS 可以按任何顺序选择相邻的邻居，我们还假设该算法总是按递增的数字顺序选择它们。

现在用 root 1 在您的头脑或您的计算机中尝试运行算法。首先，算法将使用 1-2、2-3 等之间的边在 n-1 步中到达 n。然后在回溯之后，算法移动到 1 的第二个邻居，即 3。这次将有 n-2 个步骤。相同的过程将重复，直到算法最终看到 1-n。该算法将需要 O(n ^ 2) 而不是 O(n) 步来完成。请记住 V = n & E = 2 * n - 3。所以它不是 O(V + E).

实际上，您所描述的算法在未加权图上的复杂度始终为 O(V^2)。我将把这个说法的证明留作 reader.

的练习

O(V^2) 还不错。特别是如果图形是密集的。但是由于BFS已经在O(V + E)中给出了答案，所以没有人使用DFS来计算最短距离。

Answer 3

在未加权的图中，您可以使用广度优先搜索（不是 DFS）在 O(E) 时间内找到最短路径。

事实上，如果所有的边都具有相同的权重，那么 Dijkstra 算法和广度优先搜索几乎是等价的——从不调用 reduceKey()，优先级队列可以替换为 FIFO 队列，因为新添加的顶点的权重永远不会小于之前添加的顶点。

您对 DFS 的修改不起作用，因为一旦您访问了一个顶点，您将不会再次检查它的子节点，即使它的权重发生变化。如果您在 S->B

之前遵循 S->A，您将得到此图的错误答案

S---->A---->C---->D---->E---->T
 \               /
  ------->B-----/

我们不能在未加权的图中通过 DFS（改进的 DFS）找到最短路径吗？如果不是，那为什么？

Can't we find Shortest Path by DFS(Modified DFS) in an unweighted Graph? and if not then Why?

algorithm

graph

depth-first-search