Graphs/Shortest Path

Notes

Unweighted Graphs

To find the shortest path from a vertex u to a vertex v on an unweighted graph (where "distance" is measured by number of edges), 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

Weighted Graphs

Weighted graphs assign a weight w(e) to each edge e. For an edge e connecting vertex u and v, the weight of edge e can be denoted w(e) or w(u,v).

To find the shortest path on a weighted graph, just doing a breadth-first search isn't enough - the BFS is only a measure of the shortest path based on number of edges.

If G is a weighted graph, the length/weight of a path is the sum of the weights of the edges that compose the path. For a path P connecting vertices v0 through vk, this is written:

$ w(P) = \sum_{i=0}^{k-1} w(v_i, v_{i+1}) $

The distance d(u,v) between two vertices u and v is the length/weight of the shortest path from u to v.

For a single source vertex s, finding the shortest path to all other nodes by using a greedy heuristic. This means iterating through each edge connected to a vertex, starting with the smallest weight (assuming you want to minimize distance).

Dijkstra's algorithm is a weighted breadth first search. See Graphs/Dijkstra.