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

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 4

If the question is whether or not DFS can find a shortest path in unweighted or weighted graph: the answer is YES!

You simply have to traverse ALL possible paths from source to destination and keep the minimum path sum.

If the question is whether or not this is optimal: obviously no. You are exploring all possible paths from source to destination which would mean revisiting nodes again and again which is not ideal.

So in a nutshell, DFS CAN find the shortest path in a unweighted and weighted graph, it is just not the best solution to do this.

P.S. The people who say DFS CAN'T find a shortest path, they are probably referring to the fact that if you reach the destination node from the source node, the current path you used is not guaranteed to be optimal. Which is why I said it is necessary to explore ALL paths in DFS. However, this doesn't mean it is not possible.

Answer 5

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 6

Your DP(DFS) algorithm is probably eliminating the optimal path due to the visited nodes list. In order to avoid cycles (infinite loop), DP(DFS) algorithm would end up with a solution that is not optimal. (Refer the dotted area in the graph)

Consider the graph in the picture Source is hbo Target is qbx. Words ["abo","hbw","abq","qbq","qbx","qbw"]

Problem Statement (World Ladder Problem): Words are vertices. And if you can move from one word to another word by just changing one letter, then there there is a connection(edge) between the vertices. Problem statement asks you to find a shortest path to reach from source to target word.

DP algoritm first chooses the path (PATH1) hbo->abo->abq->qbq->qbw->hbw

At this state, it would try to make the next move hbw->qbw, but it wont be able to because qbw is already visited in this path. So the dp algorithm would determine that there are no ways to reach the target(qbx) from hbw.

So later when the algorithm attempts to make the optimal PATH 2 hbo->hbw->qbw->qbx, the process is cut off at the node hbw, as PATH1 determined that you cant reach the target from hbw.

So it would endup choosing some other non optimal path like PATH 3 hbo->abo->abq->qbq->qbx.

Sample Graph

Just get the job done with BFS here.

Note: DFS without memoization would give the the optimal path but time complexity would be exponential.

Answer 7

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).

Answer 8

My understanding on using dfs for finding shortest path on unweighted graph as well as for smallest weighted path on weighted graph:

A) Dfs also can solve shortest path (also, smallest weighted path). The only cons would be the exponential time complexity arising from multiple edges revisiting already visited nodes.

B) If the requirement was to find length of shortest path (also, smallest weight): caching the distance from source to current node might seem to solve the above mentioned time complexity issue at first. But infact no, it still doesnt. Because each time a better distance comes in for a cached node (ie, distance of new path from source to current node being lesser than already cached distance at the current node), the node has to be recomputed again.

C) Conclusion: Dfs solves the shortest path (also smallest weight) problem, but its never optimal. Instead it worst in time (read exponential).