7
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ The most common pathfinding algorithm on unweighted graphs is A*, with the slight modification that ties are broken closer to the finish. This will give an algorithm similar to DFS, in that it will try the most direct route first, and only bubble outwards if it needs to. $\endgroup$ – BlueRaja - Danny Pflughoeft Oct 7 '12 at 9:54
  • 1
    $\begingroup$ Try using DFS on some (well-chosen) graphs; if it really doesn't work, you should encounter problems. Btw, your question reads as if it worked on weighted graphs. $\endgroup$ – Raphael Oct 7 '12 at 13:03
9
$\begingroup$

The only element of depth-first search you tweak is the order in which children are investigated. The normal version proceeds in arbitrary order, i.e. in the order the children are stored.

The only feasible alternative (towards shortest paths) I can come up with is a greedy approach, that is looking at children in order of their distance from the current node (from small to large). It is easy to construct a counterexample for this rule:

counter example for greedy rule
[source]

Now, that is no proof that there does not exist a strategy of choosing the next child to be investigated which will make DFS find shortest paths.

However, no matter the rule¹ you can construct graphs that have DFS commit to a long detour at the very first node, just as I did for the greedy rule. Assign edges $(s,t)$ and $(s,a)$ weights such that the rule chooses to visit $a$ first, and assign $(a,b)$ a weight greater than the one of $(s,t)$. Therefore, it is plausible that DFS can never find shortest paths (in general graphs).

Note that since you can express every (positive-integer-)weighted graph as unweighted graph -- simply replace edges with cost $c$ with a chain with $c-1$ nodes -- the same examples deal with DFS on unweighted graphs. Here, the situation is actually even more bleak: without weights, what can DFS use to determine the next child to visit?


  1. As long as the rule is deterministic. If it is not, it can clearly not always find shortest paths.
$\endgroup$
  • $\begingroup$ Correct me if I am wrong, but does this mean that DFS can find the shortest path in any graph, but will take exponential time while doing so? $\endgroup$ – Anmol Singh Jaggi Feb 22 '17 at 7:06
  • $\begingroup$ @AnmolSinghJaggi No. DFS only ever finds one path. $\endgroup$ – Raphael Feb 22 '17 at 9:58
9
$\begingroup$

Breadth-first-search is the algorithm that will find shortest paths in an unweighted graph.

There is a simple tweak to get from DFS to an algorithm that will find the shortest paths on an unweighted graph. Essentially, you replace the stack used by DFS with a queue. However, the resulting algorithm is no longer called DFS. Instead, you will have implemented breadth-first-search.

The above paragraph gives correct intuition, but over-simplifies the situation a little. It's easy to write code for which the simple swap does give an implementation of breadth first search, but it's also easy to write code that at first looks like a correct implementation but actually isn't. You can find a related cs.SE question on BFS vs DFS here. You can find some nice pseudo-code here.

$\endgroup$
1
$\begingroup$

You can!!!

Mark the nodes as visited while you are going depth and unmark while you return, while returning as you find another branch(es) repeat same.

Save cost/path for all possible search where you found the target node, compare all such cost/path and chose the shortest one.

The big(and I mean BIG) issue with this approach is that you would be visiting same node multiple times which makes dfs an obvious bad choice for shortest path algorithm.

$\endgroup$
  • 1
    $\begingroup$ You may want to note that this changes the complexity immensely. This would potentially explore every possible path from $s$ to $t$ if I'm understanding it correctly. $\endgroup$ – ryan Apr 17 at 21:00
  • 1
    $\begingroup$ @user2407394 Have you actually implemented this variation of DFS once and run it correctly for a moderately large graph? I would be hesitant to call this variation as DFS. I would call it depth-first path-exhausting search. $\endgroup$ – Apass.Jack Apr 17 at 21:14
0
$\begingroup$

BFS has a nice property that it will check all the edges from the root and keep the distance from the root to the other nodes as minimal as possible, but dfs simply jumps to the first adjacent node and goes depth wise. You CAN modify DFS to get the the shortest path, but you will only end up in an algorithm that be of higher time complexity or will end up doing the same thing BFS does

$\endgroup$
-2
$\begingroup$

IT is possible to find the path between two vertices with the minimum number of edges using DFS. we can apply level approach

$\endgroup$
  • 1
    $\begingroup$ Please give more detail. I can't tell what algorithm you're trying to describe in this single sentence. $\endgroup$ – David Richerby Aug 10 '15 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.