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.
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:
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.
Graphsnotes on graph theory, graph implementations, and graph algorithms
Part of Computer Science Notes
Series on Data Structures
Flags · Template:GraphsFlagBase · e