Skip to main content
Tweeted twitter.com/#!/StackCompSci/status/255595559115710464
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Source Link
The Unfun Cat
  • 1.8k
  • 2
  • 18
  • 29

Why can't DFS be used to find shortest paths in unweighted graphs?

I understand that using DFS "as is" will not find a shortest path in an unweighted graph.

But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? All texts on the subject simply state that it cannot be done. I'm unconvinced (without having tried it myself).

Do you know any modifications that will allow DFS to find the shortest paths in unweighted graphs? If not, what is it about the algorithm that makes it so difficult?