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.