Shortest path: DFS, BFS or both?

Question

I know BFS alone can find the shortest path in an unweighted graph but I also read on a couple of sites where people were claiming that either BFS or DFS could do this. I just wanted to confirm that these were probably mistakes and that only BFS can do this (I wasn't completely confident even after doing a quick google search). If I'm incorrect, can someone please explain how it's possible for DFS to give shortest path.

Answer 1

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

As an example, consider a graph formed by taking the corners 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 unless you follow the edge directly connecting the start and destination nodes.

As @nhahtdh notes below, there’s a variant of DFS called iterative deepening in which you run DFS with a maximum depth of one, then two, then three, etc. until you find your target. This will always find the shortest path, and does so using less memory than BFS.

Hope this helps!

Answer 2

Iterative deepening search (IDS), which consists of many rounds of depth-limited search (basically DFS, but stop searching if you have reached a depth limit d) that gradually increase the depth from 1, will find the shortest path in an 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, since you gradually increase the distance allowed from the start node: a node that has distance a + 1 will not be explored before a node that has distance a, due to the limit on depth.

One common concern is the nodes with distance a will be re-visited (d - a + 1) times where d is the depth of the shortest path to goal. It depends on the graph or search tree if we want to talk about performance. On a search tree with large branching factor, the nodes generated at depth d becomes the dominant term, so there is not much of a problem with revisiting. BFS unusable for such case due to the exponential space requirement, but IDS will only use polynomial space.

Answer 3

A perspective to understand: BFS in a graph with no weight and direction is the same as Dijkstra(weight=1, one direction), so understanding why Dijkstra is right might help. More details will be added if I have made it through.

Answer 4

I know it late for the party here but. There are several differences between DFS and BFS (short answer: Both of them can find the shortest path in the unweighted graph).

1. BFS: Usually implementing by the queue (first in the first out data structure) When you exhaust all the neighbor vertices layer by layer till you reach a destination node and halt at that node, Ex: you reach all the node from layer 1 if not found all that node layer into the queue, and keep doing for layer 2 and so on. It will guarantee the target node will be the shortest layer found so far (Because it halts after found target node, it will not traverse all the nodes in the graph (it faster than DFS in term of speed))

2. DFS: Usually implementing by the stack (first in last out data structure) DSF exhausts all the nodes from a given point until it can't explore anymore. but when it found the target node there is no guarantee that the path is the shortest path so it has to traverse all the nodes in the graph to make sure that the path is the shortest. btw

@alandong answer is wrong

Answer 5

Both BFS and DFS will give the shortest path from A to B if you implemented right.

Let's think the whole graph as a tree. Basically, BFS will run each level of tree and find out the path by traverse all the levels. In the contrast, DFS will run to each leaf nodes and find out the path when traverse node along that path. Both of them are using exhaust path-finding search, so, both of them will guarantee to find the shortest path, again if you implemented these algorithms correctly.

The pros and cons for using BFS and DFS is the following:

BFS, uses more memory, traverse all nodes

DFS, uses less memory, might be slightly faster if you are lucky to pick the leaf node path contains the node you are interested in.(Don't necessarily have to traverse all nodes).