The shortest path: DFS, BFS, or both?

Question

I know that only BFS can find the shortest path on an unweighted chart, but I also read on several sites where people claimed that BFS or DFS could do this. I just wanted to confirm that these are probably errors and that only BFS can do this (I was not completely sure even after a quick Google search). If I'm wrong, can someone explain how it is possible for DFS to give the shortest path.

Answer 1

DFS does not necessarily display the shortest paths in an undirected graph. BFS would be the right choice here.

As an example, consider a graph formed by taking the angles of a triangle and connecting them. If you try to find the shortest path from one node to another using DFS, then you will get the wrong answer if you do not follow the edge directly connected to the start and end nodes.

Hope this helps!

Answer 2

An iterative recess search (IDS), which consists of many rounds of depth searches (mainly DFS, but stop searching if you reach the depth limit d), which gradually increases the depth from 1, will find the shortest path to the unweighted graph.

// Iterative deepening search // isGoal is a function that checks whether the current node is the goal function ids(graph, start, isGoal) { maxDepth = 1 do { found = dls(graph, start, isGoal, maxDepth, 0) // Clear the status whether a node has been visited graph.clearVisitedMarker(); // Increase maximum depth depth = depth + 1 // You can slightly modify the dls() function to return whether there is a // node beyond max depth, in case the graph doesn't have goal node. } while (found == null) return found } // Depth-limited search // isGoal is a function that checks whether the current node is the goal function dls(graph, currentNode, isGoal, maxDepth, currentDepth) { if (graph.visited(currentNode)) { return null } graph.setVisited(currentNode) if (isGoal(currentNode)) { return currentNode } // Stop searching when exceed max depth // This is the only difference from DFS if (currentDepth >= maxDepth) { return null } for (adjNode in graph.getAdjacent(currentNode)) { found = dls(graph, adjNode, goal, maxDepth, currentDepth + 1) if (found != null) { return found } } return null } 

It works, as you gradually increase the distance allowed from the beginning of a node: a node with a distance of a + 1 will not be studied to a node having a distance a, due to the depth limit.

One common problem is that nodes with distance a will be re-visited (d - a + 1) times, where d is the depth of the shortest path to the target. It depends on the graph or search tree if we want to talk about performance. In the search tree with a large branching coefficient, nodes generated at depth d become dominant, so there are not so many problems with the transition. BFS is unsuitable for this case due to the exponential space requirement, but IDS will only use polynomial space.

Answer 3

Perspective for understanding: BFS in a graph without weight and direction coincides with Dijkstra (weight = 1, in one direction), so understanding why Dijkstra is right can help. More details will be added if I have completed it.

Answer 4

Both BFS and DFS will give the shortest path from A to B if you applied it correctly.

Think of the whole graph as a tree. Basically, BFS will run each level of the tree and determine the path, going through all levels. In contrast, DFS will run on each leaf node and recognize the path when the node crosses along that path. Both of them use the search for exhaust search paths, so both of them guarantee the search for the shortest path if you correctly performed these algorithms.

The pros and cons of using BFS and DFS are as follows:

BFS, uses more memory, moves all nodes

DFS uses less memory, it might be a little faster if you are lucky enough to select a node sheet containing the node of interest to you (optional to go through all the nodes).