Is BFS traversal the same as DFS in a Complete Undirected Graph?

Question

I have an assignment which requires me to calculate the shortest path given a complete undirected graph. The question is given a complete undirected graph, the basic algorithm(BFS and DFS) can provide the shortest path. I wonder whether using BFS or DFS would produce me the same output considering that it is a complete undirected graph.

Answer 1

I assume the graph is weighted with non-negative weights

• the shortest path is trivial in an unweighted complete graph
• in an undirected graph, a negative weight edge will create a negative weight cycle. There's no shortest path in such graph, because you can always improve it by adding the negative cycle.

I also assume you're looking for a shortest path between two given vertices, as that's the only shortest path task where both DFS and BFS are really applicable.

• to find all single-source shortest path, you'd use Dijkstra
• to find all pairs shortest path, you'd use Floyd-Warshall

If the graph is finite, both DFS and BFS will give you the shortest path. If there's multiple shortest paths, both DFS and BFS can be done so they return all of them. Otherwise, they're not guaranteed to give you the same shortest path - that's not even guaranteed for different implementations of the same algorithm, it may differ based on the ordering of edges.

Both DFS and BFS will have a terrible time complexity O(n!) as they will traverse over the whole problem space, finding all possible paths from the source to target. Additionaly, BFS will have a much bigger space complexity (O(n!) again).

For both DFS and BFS, this complexity can be somewhat improved in the average case by keeping a "current best" and pruning branches that can't beat it (as their length is already worse). But you're still getting nowhere near the speed of more suitable algorithms, like Dijkstra or A*