Skip to interview prep
Apexed

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).

Does DFS find shortest paths in an unweighted graph — Data structures & algorithms interview question — Apexed