Java Reference
In-Depth Information
(Figure 28-14 continued)
(h)
(g)
cs3
cs6
cs8
cs3
cs6
cs8
cs1
cs2
cs4
cs7
cs9
cs10
cs10
cs1
cs2
cs4
cs7
cs9
cs5
cs5
(j)
(i)
cs3
cs6
cs8
cs3
cs6
cs8
cs1
cs2
cs4
cs7
cs9
cs10
cs1
cs2
cs4
cs7
cs9
cs10
cs5
cs5
Learning whether a particular airline flies between two given cities is important to the average
traveler. We can obtain this information by using a graph—such as the one in Figure 28-6—to
represent the airline's routes and testing whether a path exists from vertex
a
to vertex
b
. If a path
exists, we can also find out what it is. If not any path will do, we can find the one that is shortest
or cheapest.
28.16
For the moment we are content to find any path, not necessarily the best one. A depth-first
traversal—discussed in Segment 28.13—stays on a path through the graph as it visits as many
vertices as possible. We can easily modify this traversal to locate a path between two vertices.
We begin at the origin vertex. Each time we visit another vertex, we see whether that vertex is
the desired destination. If so, we are done and the resulting stack contains the path. Other-
wise, we continue the traversal until either we are successful or the traversal ends. We leave
the development of this algorithm as an exercise.
28.17
Example.
A graph can have several different paths between the same two vertices. In an unweighted
graph, we can find the path with the shortest length, that is, the path that has the fewest edges. For
example, consider the unweighted graph in Figure 28-15a. Suppose that we want to know the shortest
path from vertex
A
to vertex
H
. By inspecting the graph, we can see that several simple paths—shown
in Part
b
of the figure—are possible between these two vertices. The path from
A
to
E
to
H
has length
2 and is the shortest.
