BFS与DFS的标准实现是否能保证找到给定图的最短路径？

先明确前提：这里讨论的「最短路径」指总权重最小的路径（无权图可默认所有边权重为1）。

标准BFS的表现 #

• 仅当所有边的权重完全相同时，标准BFS能可靠找到最短路径。因为BFS是按「边的数量（层级）」遍历的，第一次抵达目标节点的路径，既是边数最少的，也是总权重最小的。
• 一旦图中存在不同权重的边，标准BFS完全无法保证找到总权重最小的路径。举个例子：起点到终点有一条直接边权重为10，同时存在一条经过2个中间节点的路径，总权重仅为3。BFS会先遍历到那条直接边，错误地将其判定为最短路径。

标准DFS的表现 #

• 无论边权重是否相同，标准DFS都不能保证找到最短路径。DFS的逻辑是沿着一条路径走到尽头再回溯，遍历顺序和路径的总权重没有任何关联。它可能在第一次找到目标节点时，走的是一条总权重极大的路径，而更优的路径还没被遍历到。
• 当然极端场景下（比如图中只有唯一一条路径），DFS会刚好找到这条路径，但这只是巧合，完全不是算法本身的特性。

总结 #

• 仅在所有边权重相同的图中，标准BFS具备找最短路径的能力；权重不同时，BFS不适用。
• 标准DFS从设计逻辑上就不针对最短路径问题，无论何种带权图，都不能依赖它来找最短路径。
• 如果需要在任意带权图（含不同权重、甚至负权重场景）中找最短路径，应该使用Dijkstra（无负权边）、Bellman-Ford（允许负权边但无负环）这类专门的最短路径算法。

内容的提问来源于stack exchange，提问作者SoRRoW.DaDa