Shortest Paths
See also: Graph Problems, S-T Connectivity, Tree vs Graph Traversals
Graph Problems Summary
| Problem | Description | Efficiency |
|---|---|---|
| S-T paths | Find a path from s to every reachable vertex | |
| S-T shortest paths | Find a shortest path from s to every reachable vertex |
Last time, we saw two ways to find paths in a graph: DFS and BFS.
Which is better?