next up previous contents index CD CD Algorithms
Next: Dijkstra's Algorithm Up: Graph Algorithms Previous: Kruskal's Algorithm

Shortest Paths

Figure: The shortest path from to t can pass through many intermediate vertices.  

The shortest path between two vertices and t in an unweighted graph can be constructed using a breadth-first search from . When we first encounter t in the search, we will have reached it from using the minimum number of possible edges. This minimum-link path is recorded in the breadth-first search tree, and it provides the shortest path when all edges have equal weight. However, in an arbitrary weighted graph, the weight of a path between two vertices is the sum of the weights of the edges along the path. The shortest path might use a large number of edges, just as the shortest route (timewise) from home to office may involve shortcuts using backroads and many turns, as shown in Figure gif.  

Shortest paths have a surprising variety of applications. See catalog Section gif and the war story of Section gif for further examples.

Mon Jun 2 23:33:50 EDT 1997