Can't we find Shortest Path by DFS(Modified DFS) in an unweighted Graph? and if not then Why?

Question

It is said that DFS can't be used to find the shortest path in the unweighted graph. I have read multiple post and blogs but not get satisfied as a little modification in DFS can make it possible.

I think if we use Modified DFS in this way, then we can find the shortest distances from the source.

1. Initialise a array of distances from root with infinity and distance of root from itself as 0.
2. While traversing, we keep track of no. of edges. On moving forward increment no. of edges and while back track decrement no. of edges. And each time check if(dist(v) > dist(u) + 1 ) then dist(v) = dist(u) + 1.

In this way we can find the shortest distances from the root using DFS. And in this way, we can find it in O(V+E) instead of O(ElogV) by Dijkstra.

If I am wrong at some point. Please tell me.

Answer 1

Yes, if the DFS algorithm is modified in the way you mentioned, it can be used to find the shortest paths from a root in an unweighted graph. The problem is that in modifying the algorithm you have fundamentally changed what it is.

It may seem like I am exaggerating as the change looks minor superficially but it changes it more than you might think.

Consider a graph with n nodes numbered 1 to n. Let there be an edge between each k and k + 1. Also, let 1 be connected to every node.

Since DFS can pick adjacent neighbors in any order, let's also assume that this algorithm always picks them in increasing numerical order.

Now try running algorithm in your head or your computer with root 1. First the algorithm will reach n in n-1 steps using edges between 1-2, 2-3 and so on. Then after backtracking, the algorithm moves on to the second neighbor of 1, namely 3. This time there will be n-2 steps. The same process will repeat until the algorithm finally sees 1-n. The algorithm will need O(n ^ 2) rather than O(n) steps to finish. Remember that V = n & E = 2 * n - 3. So it is not O(V + E).

Actually, the algorithm you have described will always finish in O(V^2) on unweighted graphs. I will leave the proof of this claim as an exercise for the reader.

O(V^2) is not that bad. Especially if a graph is dense. But since BFS already provides an answer in O(V + E), nobody uses DFS for shortest distance calculation.

Answer 2

In an unweighted graph, you can use a breadth-first search (not DFS) to find shortest paths in O(E) time.

In fact, if all edges have the same weight, then Dijkstra's algorithm and breadth-first search are pretty much equivalent -- reduceKey() is never called, and the priority queue can be replaced with a FIFO queue, since newly added vertices never have smaller weight than previously-added ones.

Your modification to DFS does not work, because once you visit a vertex, you will not examine its children again, even if its weight changes. You will get the wrong answer for this graph if you follow S->A before S->B

S---->A---->C---->D---->E---->T
 \               /
  ------->B-----/