244. Does DFS find shortest paths in an unweighted graph?
EasyGraph algorithms
Technical
Show model answer
No. DFS follows one branch as deep as possible, so the first time it reaches a vertex may be through a long detour; for example in a triangle a-b-c it may reach c via b instead of directly. The DFS tree path is a path, not necessarily the shortest.
Use BFS for unweighted shortest paths (O(V + E)), 0-1 BFS for weights 0 and 1, Dijkstra for non-negative weights and Bellman-Ford when weights can be negative. In a DAG, relaxing edges in topological order gives shortest (or longest) paths in O(V + E).