Graphs/Shortest Path
From charlesreid1
Notes
Unweighted Graphs
To find the shortest path from a vertex u to a vertex v on an unweighted graph, we can use a breadth-first search. A BFS results in a BFS tree; if two vertices u and v are connected by the BFS, then the BFS tree yields the shortest path by definition. This works for both directed and undirected graphs.
See Graphs/BFS.
Flags
