最短路径:DFS,BFS或两者兼而有之？

Question

我知道单独的BFS可以找到未加权图中的最短路径,但我也读过几个人们声称BFS或DFS可以做到这一点的网站.我只想确认这些可能是错误,而且只有BFS可以做到这一点(即使在快速谷歌搜索后我也没有完全自信).如果我不对,请有人解释一下DFS如何能够提供最短的路径.

Answer 1

DFS不一定在无向图中产生最短路径.BFS将是这里的正确选择.

例如,考虑通过取三角形并连接它们而形成的图形.如果您尝试使用DFS找到从一个节点到另一个节点的最短路径,那么除非您遵循直接连接起始节点和目标节点的边缘,否则您将得到错误的答案.

希望这可以帮助!

Answer 2

迭代深化搜索 (IDS)，由多轮深度限制搜索（基本上是 DFS，但如果达到深度限制 d 则停止搜索）组成，从 1 逐渐增加深度，将在未加权图中找到最短路径.

// Iterative deepening search
// isGoal is a function that checks whether the current node is the goal
function ids(graph, start, isGoal) { 
    maxDepth = 1
    do {
        found = dls(graph, start, isGoal, maxDepth, 0)
        // Clear the status whether a node has been visited
        graph.clearVisitedMarker();
        // Increase maximum depth
        depth = depth + 1

    // You can slightly modify the dls() function to return whether there is a
    // node beyond max depth, in case the graph doesn't have goal node.
    } while (found == null)

    return found
}

// Depth-limited search
// isGoal is a function that checks whether the current node is the goal
function dls(graph, currentNode, isGoal, maxDepth, currentDepth) {
    if (graph.visited(currentNode)) {
        return null
    }
    graph.setVisited(currentNode)

    if (isGoal(currentNode)) {
        return currentNode
    }

    // Stop searching when exceed max depth
    // This is the only difference from DFS
    if (currentDepth >= maxDepth) {
        return null
    }

    for (adjNode in graph.getAdjacent(currentNode)) {
        found = dls(graph, adjNode, goal, maxDepth, currentDepth + 1)
        if (found != null) {
            return found
        }
    }

    return null
}

它有效，因为您逐渐增加了与起始节点允许的距离：由于深度的限制，距离为 a + 1 的节点不会在距离为 a 的节点之前被探索。

一个常见的问题是距离为 a 的节点将被重新访问 (d - a + 1) 次，其中 d 是到达目标的最短路径的深度。如果我们想谈论性能，这取决于图或搜索树。在分支因子较大的搜索树上，深度d生成的节点成为主导项，因此重访问题不大。由于指数空间要求，BFS 无法用于这种情况，但 IDS 将仅使用多项式空间。

Answer 3

我知道这里的聚会已经很晚了，但是。DFS 和 BFS 之间有几个区别（简短的回答：它们都可以在未加权的图中找到最短路径）。

1. BFS：通常通过队列实现（先进先出数据结构）当您逐层耗尽所有邻居顶点直到到达目标节点并停在该节点时，例如：如果没有到达则从第1层到达所有节点找到所有该节点层放入队列中，并继续执行第 2 层，依此类推。它将保证目标节点将是迄今为止找到的最短的层（因为它在找到目标节点后停止，因此不会遍历图中的所有节点（速度上比DFS更快））

2. DFS：通常通过堆栈（先进后出数据结构）实现，DSF从给定点耗尽所有节点，直到无法再探索为止。但是当它找到目标节点时，并不能保证该路径是最短路径，因此它必须遍历图中的所有节点以确保该路径是最短路径。顺便提一句

@alandong 答案是错误的

Answer 4

如果问题是 DFS 能否在未加权或加权图中找到最短路径：答案是 YES！

您只需遍历从源到目的地的所有可能路径并保持最小路径总和。

如果问题是这是否是最佳的：显然不是。您正在探索从源到目的地的所有可能路径，这意味着一次又一次地重新访问节点，这并不理想。

简而言之，DFS 可以在未加权和加权图中找到最短路径，但这并不是最好的解决方案。

PS 那些说DFS不能找到最短路径的人，他们可能指的是这样一个事实：如果你从源节点到达目的节点，你当前使用的路径并不能保证是最优的。这就是为什么我说有必要探索 DFS 中的所有路径。然而，这并不意味着这是不可能的。