# 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?

• 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. – BlueRaja - Danny Pflughoeft Oct 7 '12 at 9:54
• 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. – Raphael Oct 7 '12 at 13:03
• yes, you can do it. Here is the solution – Anmol Middha Jun 12 '19 at 7:52

## 7 Answers

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: [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.
• 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? – Anmol Singh Jaggi Feb 22 '17 at 7:06
• @AnmolSinghJaggi No. DFS only ever finds one path. – Raphael Feb 22 '17 at 9:58
• Wait, with DFS can't I list all the paths from source to a destination using backtracking.? I can just take a min of all the paths then. – piepi Apr 1 at 2:54
• @piepi "DFS with backtracking" is not DFS; two different algorithms. Most notably, DFS has linear running-time whereas "DFS with backtracking" has super-exponential worst-case running time. – Raphael Apr 1 at 11:08

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.

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.

• 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. – ryan Apr 17 '19 at 21:00
• @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. – John L. Apr 17 '19 at 21:14
• I ve implemented this kind of approach, its working really slow. Im thinking about adding mnemonization to improve performance. – Mic Jul 9 '19 at 9:43
• @user2407394 it seems like it'd work, but how do you check for when to stop as there'd be no 'visited' list if you unmark them all? – Joe Black Mar 1 '20 at 6:37
• @JoeBlack your base case still remains the same as in the original DFS - return if there is no undiscovered neighbor node (for shortest path, there is an additional base case - if the node is destination then return right away). The node is unmarked once ALL of its children return, not earlier. So for its children, the caller will still be marked as discovered – mangusta Apr 30 '20 at 17:33

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

i think you can find the shortest path using slightly tweaked version of DFS . This is what i have came up with.

struct visited{
bool v;
int src;
int dest;
visited():v{0},src{INT32_MIN},dest{INT32_MIN}{
}
};
void setvisit(bool val,int src,int dest,visited & obj){
obj.src=src;
obj.v=val;
obj.dest=dest;
}
bool check(visited & obj,int src,int dest,visited * v){
if(obj.v){
if(obj.src !=src && obj.dest==dest){
visited v1=v[src];
if(v1.src==dest && v1.dest==src && v1.v){
return false;
}else{return true;}
}else if(obj.src==INT32_MIN && obj.dest==INT32_MIN){
return true;
}else{
return false;
}
}else{
return true;
}
}
void Dfs(int src,int & res,int dest,std::vector<int> g[],visited ** visit,int count){
visited *v=*visit;
for(int i=0;i<g[src].size();i++){
if(check(v[g[src][i]],src,g[src][i],v)){
if(g[src][i]==dest){
res=std::min(res,count+1);
return;
}else{
setvisit(1,src,g[src][i],v[g[src][i]]);
}
Dfs(g[src][i],res,dest,g,visit,count+1);
}
}
}
int shortestPath(int src,int dest,std::vector<int> g[],int n){
if(src==dest){return 0;}
visited * visit=new visited[n];
setvisit(1,src,INT32_MIN,visit[src]);
int res=INT32_MAX;
Dfs(src,res,dest,g,&visit,0);
delete [] visit;
return res;
}


I might be wrong but until now all the test cases i have tried it has worked. i have used these rules to make modifications in DFS

1. you cannot go to source again from any other edge i.e you can never travel from any other edge towards source edge.
2. if there are two edge A & B with B !=destination_edge with an undirected edge connecting them
i.e A------B then
a. if we travelled through A to B then
a1. we cannot travel from B to A using same edge.
a2. we can always travel from A to B again using same edge if we again somehow land at edge A.
3.  you can travel directly towards destinaton any number of times from any edge i.e A-----dest.
then you can travel towards destination from A again an again using same edge.

• Could you add explanation? What is the tweak about? – Evil Oct 31 '20 at 16:08

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

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

You can

just traverse the graph in dfs manner and check

if(distance[dest] > distance[source]+cost[source_to_destination]){
distance[dest] = distance[source] + cost[source_to_destination]);
}


Here is the link for full solution

• The accepted answer claims this is not possible, which contradicts your claim. Can you explain why you think that nevertheless this approach works? (or explain why this approach works in general) – Discrete lizard Jun 12 '19 at 8:36
• Isn't this just repeating user2407394's answer, only with hard-to-understand code (you've not defined what any of those variables mean, and it's not obvious, to me) instead of an explanation? – David Richerby Jun 12 '19 at 9:08
• Yes, it is the implementation of user2407394's answer. Sorry for inconvenience. I have added comments in code. You can check it now. – Anmol Middha Jun 13 '19 at 4:43