29
$\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?

Improve this question
$\endgroup$
3
  • 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
    Commented Oct 7, 2012 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
    Commented Oct 7, 2012 at 13:03
  • $\begingroup$ yes, you can do it. Here is the solution $\endgroup$
    – Anmol Middha
    Commented Jun 12, 2019 at 7:52

8 Answers 8

Reset to default
15
$\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.
Improve this answer
$\endgroup$
4
  • 1
    $\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
    Commented Feb 22, 2017 at 7:06
  • $\begingroup$ @AnmolSinghJaggi No. DFS only ever finds one path. $\endgroup$
    – Raphael
    Commented Feb 22, 2017 at 9:58
  • 3
    $\begingroup$ 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. $\endgroup$
    – piepi
    Commented Apr 1, 2021 at 2:54
  • 2
    $\begingroup$ @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. $\endgroup$
    – Raphael
    Commented Apr 1, 2021 at 11:08
12
$\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.

Improve this answer
$\endgroup$
8
$\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.

Improve this answer
$\endgroup$
6
  • 2
    $\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
    Commented Apr 17, 2019 at 21:00
  • 3
    $\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$
    – John L.
    Commented Apr 17, 2019 at 21:14
  • $\begingroup$ I ve implemented this kind of approach, its working really slow. Im thinking about adding mnemonization to improve performance. $\endgroup$
    – Mic
    Commented Jul 9, 2019 at 9:43
  • 2
    $\begingroup$ @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? $\endgroup$
    – Joe Black
    Commented Mar 1, 2020 at 6:37
  • 1
    $\begingroup$ @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 $\endgroup$
    – mangusta
    Commented Apr 30, 2020 at 17:33
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

Improve this answer
$\endgroup$
-1
$\begingroup$

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.
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Could you add explanation? What is the tweak about? $\endgroup$
    – Evil
    Commented Oct 31, 2020 at 16:08
-2
$\begingroup$

DFS can be implemented with slight backtracking but it is not feasible , on a unweighted going with bfs is better since it moves level by level.

DFS code:

void shortestPathDFS(vector<vector<int>>& graph, int current, int destination, vector<int>& path, vector<int>& shortestPath, unordered_set<int>& visited) {

visited.insert(current);

path.push_back(current);

if (current == destination) {
    if (shortestPath.empty() || path.size() < shortestPath.size()) {
        shortestPath = path;
    }
     return;
}

for (int neighbor : graph[current]) {
    if (visited.find(neighbor) == visited.end()) {
        shortestPathDFS(graph, neighbor, destination, path, shortestPath, visited);
    }
}

path.pop_back();
visited.erase(current);

}

Improve this answer
$\endgroup$
-3
$\begingroup$

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

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

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

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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) $\endgroup$
    – Discrete lizard ♦
    Commented Jun 12, 2019 at 8:36
  • $\begingroup$ 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? $\endgroup$
    – David Richerby
    Commented Jun 12, 2019 at 9:08
  • $\begingroup$ Yes, it is the implementation of user2407394's answer. Sorry for inconvenience. I have added comments in code. You can check it now. $\endgroup$
    – Anmol Middha
    Commented Jun 13, 2019 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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