**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 .

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

Mon Jun 2 23:33:50 EDT 1997