Depth First Search to find shortest path?

Question

I know this is usually done with breadth first, but we are asked to do it with both, I already accomplished breadth first....

I feel like this is a pretty typical example of using a depth first search, so I was hoping I could get some help here... I am attempting to find the shortest path through a maze using depth first search, but as of right now I cannot wrap my head around how exactly to do it. This is my code so far:

void maze::findPathRecursive(graph &g, int position, int goal) {
    if (position == goal) {
        isPath = true; //returns true if there is a path to the goal
        correctPath.push_back(position); // the path to the goal
    } else {
        g.mark(position);
        g.visit(position);

        //gets all the neighbors of the current position
        vector<int> neighbors = getNeighbors(position, g);

        while (!neighbors.empty()) {
            int n = neighbors.back();
            neighbors.pop_back();

            if (!g.isVisited(n)) {
                findPathRecursive(g, n, goal);
            } 

            if (isPath) {
                correctPath.push_back(position);
                break;
            } 
        } 
    } 
}

Right now, what this does is find the first path it can to the goal and breaks from there. I know I'll need to get rid of the break and I tried making another vector to store the shortest path and compare the lengths between it and the previous shortest but it did not work because I feel like I need to unvisit nodes at some point but cannot figure out how exactly to do it here.

Any help is greatly appreciated!!

g is a graph by the way which contains the maze.

@nobillygreen well the way it works right now is that even if it did make a big circle, the first node would be marked as visited and would not be able to be visited again, so in a way yes it is — seanscal, Mar 28 '14 at 14:52
Possible duplicate of [DFS shortest path of a maze in C++](https://stackoverflow.com/questions/22764120/dfs-shortest-path-of-a-maze-in-c) — pushkin, Nov 06 '18 at 16:49

score 1 · Answer 1 · answered Mar 28 '14 at 14:44

1

In general, you don't want to use DFS to find shortest path (unless your graph is definitively acyclic and also undirected, in which case, there is only one path to your goal to begin with.) It's possible, but it gets very contrived. On its simplest level, DFS is more adept at determining if there IS a path then determining what the best path is.

I'd recommend taking a look at different Breadth First Search (BFS) algorithms. If your maze is on a grid, A* is probably your best bet.

answered Mar 28 '14 at 14:44

nobillygreen

1,548
5
19
27

This is for an assignment we have to do both, I understand the breadth first, but depth first seems to be tripping me up – seanscal Mar 28 '14 at 14:48
"unless your graph is definitively acyclic and also undirected, in which case, there is only one path to your goal to begin with" -> That's not true, think about a root that connects to N nodes, and then all of those N nodes connect to the goal. This is an acyclic undirected graph that has several paths to the goal. – Reuben Morais May 05 '18 at 22:11
@ReubenMorais "a root that connects to N nodes, and then all of those N nodes connect to the goal" - there are lots of cycles in such graph – mangusta Jan 08 '19 at 07:18
@mangusta good point, I'm so used to thinking about *directed* acyclic graphs that I must have forgotten we were talking about *undirected* graphs. – Reuben Morais Feb 06 '19 at 18:55

score 1 · Answer 2 · answered Mar 31 '14 at 05:23

While you can find a path (and if you're lucky a shortest path) using DFS, it does not guarantee a shortest path in general. BFS is your best bet.

There is however an approach called Iterative Deepening. From Wikipedia:

Iterative deepening depth-first search1 (IDDFS) is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state. IDDFS is equivalent to breadth-first search, but uses much less memory; on each iteration, it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first.

Pseudocode, again from wikipedia:

> IDDFS(root, goal) {
>   depth = 0
>   for(i=1, i<10, i++)   {
>       DFS(limit=i)
>   }
> }

First implement a DFS (should be exactly like BFS, but use a stack instead of a queue), and then implement the ID algorithm. Hope this helps.

score 0 · Answer 3 · edited Apr 13 '17 at 12:48

I'm not sure I understand the question completely, but usually, wouldn't you use a breadth-first search (at least, in the simplest case)? It seems to me that any DFS that tries to find the shortest path has to turn into some sort of BFS anyway, as a DFS might "miss" shortcuts.

Maybe this https://cs.stackexchange.com/questions/4914/why-cant-dfs-be-used-to-find-shortest-paths-in-unweighted-graphs and this http://en.wikipedia.org/wiki/Shortest_path_problem helps.

score 0 · Answer 4 · answered May 03 '16 at 16:41

0

Rather than "unvisit" a node, I think you need to store with each node how many edges it took to get there. If you get there again via a shorter path, you update the edge count for that node and all the nodes that are on the best path from that node to the goal.

answered May 03 '16 at 16:41

Bob

1

not sure how exactly you found this question to answer it, but check the answer i've given that links to a separate question answering this problem – seanscal May 04 '16 at 15:18

Depth First Search to find shortest path?

4 Answers4

Linked