问搜索算法(BFS和DFS)也能得到最短路径吗？

EN

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

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都可以或将返回更昂贵的路径( and = 200而不是and= 3).

BFS将访问B( and )和C( and )，然后访问E( and )和D(And).此时，它将停止，因为它已经达到目标，并返回较长的路径A。

DFS可以从任意访问B或C开始，如果它首先访问C，它将返回最短的路径and，但如果它首先访问B，它将探索and并返回这条较长的路径。