# Shortest Paths

## Recalls

So far, we have methods to do the following

• find a path from a given vertex, $s$, to every reachable vertex in the graph.
• find a shortest path from a given vertex, $s$ to every reachable vertex in the graph. (...or do we?)

Before we answer the mysterious question posed above, let's further recall the two types of searches we could use to do the above two things: BFS or DFS.

Are both going to always be correct? Yes. Does one give better results? BFS finds you the shortest paths whereas DFS does not. Is one more efficient than the other, runtime-wise? No. Is one more efficient than the other, space-wise?

• DFS is worse for spindly graphs. Imagine a graph with 10000 nodes all spindly. We'll end up making 10000 recursive calls, which is bad for space.
• BFS is worse for "bushy" graphs, because our queue gets used a lot.