Graphs/Shortest Path: Difference between revisions
From charlesreid1
(→Notes) |
(→Notes) |
||
| Line 1: | Line 1: | ||
=Notes= | =Notes= | ||
To find the shortest path from a vertex u to a vertex v, 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. | ==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]]. | See [[Graphs/BFS]]. | ||
Revision as of 15:37, 9 September 2017
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
