Shortest path: DFS, BFS or both?

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!

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)