algorithm - 是否也可以使用搜索算法(BFS 和 DFS)来获得最短路径？

Question

在我的 AI 类(class)中，我学习了 BFS、DFS 和 UCS。在我的算法类(class)中，我学习了 Dijkstra 算法。

我们是否仅应用 BFS 和 DFS 等搜索算法来确定特定节点是否存在，或者它是否也像 Dijkstra 算法一样给出最短路径？

Answer 1

Dijkstra 算法只是 BFS 的推广 - 如果所有边权重都等于 1，则 BFS 在概念上与 Dijkstra 算法相同。

BFS(广度优先搜索)如果所有边权重都等于 1，将为您提供最短(如最低成本)路径，但不会(必然)否则，因为它探索节点的顺序根本不取决于边权重。

DFS(深度优先搜索)不一定会给你最短路径，因为它一次只探索一条任意路径——也许你很幸运，那条路径是最短路径，但一般来说不会的。它将为您提供树中的最短路径，但这只是因为到任何给定节点只有一条路径。

UCS(统一成本搜索)works very similarly to Dijkstra's algorithm并且还将返回最短路径，但返回到单个目标节点而不是所有其他节点。

例子

对于下图，假设我们从 A 开始到 E。

    A 1 C 1 D
    O---O---O
100 |       | 1
    O-------O
    B  100  E

BFS 和 DFS 都可以或将返回更昂贵的路径(A-B-E = 200 而不是 A-C-D-E = 3)。

BFS会访问B(A-B)和C(A-C)，然后是E(A-B-E)和D(A-C-D)。此时它会停止，因为它已经到达目标，并返回更长的路径 A-B-E。

DFS 可以从任意访问 B 或 C 开始。如果它首先访问 C，它将返回最短路径 A-C-D-E，但如果它首先访问 B，它将探索 A-B-E 并返回更长的路径。