# 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. Oct 7, 2012 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, 2012 at 13:03
• yes, you can do it. Here is the solution Jun 12, 2019 at 7:52

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? Feb 22, 2017 at 7:06
• @AnmolSinghJaggi No. DFS only ever finds one path.
– Raphael
Feb 22, 2017 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. Apr 1, 2021 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, 2021 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, 2019 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. Apr 17, 2019 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, 2019 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? Mar 1, 2020 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 Apr 30, 2020 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.

– Evil
Oct 31, 2020 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. Aug 10, 2015 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) Jun 12, 2019 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? Jun 12, 2019 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. Jun 13, 2019 at 4:43