|
|
< Day Day Up > |
|
A motorist wishes to find the shortest possible route from Chicago to Boston. Given a road map of the United States on which the distance between each pair of adjacent intersections is marked, how can we determine this shortest route?
One possible way is to enumerate all the routes from Chicago to Boston, add up the distances on each route, and select the shortest. It is easy to see, however, that even if we disallow routes that contain cycles, there are millions of possibilities, most of which are simply not worth considering. For example, a route from Chicago to Houston to Boston is obviously a poor choice, because Houston is about a thousand miles out of the way.
In this chapter and in Chapter 25, we show how to solve such problems efficiently. In a shortest-paths problem, we are given a weighted, directed graph G = (V, E), with weight function w : E → R mapping edges to real-valued-weights. The weight of path p = <v0, v1, ..., vk> is the sum of the weights of its constituent edges:
We define the shortest-path weight from u to v by
A shortest path from vertex u to vertex v is then defined as any path p with weight w(p) = δ(u, v).
In the Chicago-to-Boston example, we can model the road map as a graph: vertices represent intersections, edges represent road segments between intersections, and edge weights represent road distances. Our goal is to find a shortest path from a given intersection in Chicago (say, Clark St. and Addison Ave.) to a given inter-section in Boston (say, Brookline Ave. and Yawkey Way).
Edge weights can be interpreted as metrics other than distances. They are often used to represent time, cost, penalties, loss, or any other quantity that accumulates linearly along a path and that one wishes to minimize.
The breadth-first-search algorithm from Section 22.2 is a shortest-paths algorithm that works on unweighted graphs, that is, graphs in which each edge can be considered to have unit weight. Because many of the concepts from breadth-first search arise in the study of shortest paths in weighted graphs, the reader is encouraged to review Section 22.2 before proceeding.
|
|
< Day Day Up > |
|