Shortest path: DFS, BFS or both?

Question

I know BFS alone can find the shortest path in an unweighted graph but I also read on a couple of sites where people were claiming that either BFS or DFS could do this. I just wanted to confirm that these were probably mistakes and that only BFS can do this (I wasn't completely confident even after doing a quick google search). If I'm incorrect, can someone please explain how it's possible for DFS to give shortest path.

Answer 1

DFS does not necessarily yield shortest paths in an undirected graph. BFS would be the correct choice here.

As an example, consider a graph formed by taking the corners of a triangle and connecting them. If you try to find the shortest path from one node to another using DFS, then you will get the wrong answer unless you follow the edge directly connecting the start and destination nodes.

As @nhahtdh notes below, there’s a variant of DFS called iterative deepening in which you run DFS with a maximum depth of one, then two, then three, etc. until you find your target. This will always find the shortest path, and does so using less memory than BFS.

Hope this helps!