Java Reference
In-Depth Information
FIGURE 28-15
(a) An unweighted graph and (b) the possible paths from vertex
A
to vertex
H
(a)
(b)
A
A
A
A
A
B
B
D
E
E
E
E
G
F
H
F
H
H
H
H
A
D
G
B
E
H
C
F
I
28.18
Developing the algorithm.
The algorithm to find the shortest path between two given vertices in
an unweighted graph is based on a breadth-first traversal. Recall that this traversal visits the origin
vertex, then the origin's neighbors, the neighbors of each of these neighbors, and so on. Each vertex
is placed into a queue as it is visited.
To find the shortest path, we enhance the breadth-first traversal as follows. When we visit a
vertex
v
and mark it as visited, we note the vertex
p
that we just left to reach
v
. That is,
p
precedes
v
in the graph. We also note the length of the path that the traversal followed to reach
v
. This length is
1 more than the length of the path to vertex
p
. We place both the length of the path to
v
and a refer-
ence to
p
into vertex
v
. At the end of the traversal, we will use this data in the vertices to construct
the shortest path. Let's jump ahead to that part of the algorithm.
Figure 28-16a shows the state of the graph in Figure 28-15a after the algorithm has traversed
from vertex
A
to vertex
H
. Each vertex contains its label, the length of the path to it, and the vertex
that precedes it on this path, as shown in Figure 28-16b. Although a vertex also contains other data
fields, we have ignored them in this figure.
FIGURE 28-16
(a) The graph in Figure 28-15a after the shortest-path algorithm
has traversed from vertex
A
to vertex
H
; (b) the data in a vertex
(a)
(b)
A
0
D
1 A
G 2 D
Vertex label
Predecessor
E
1
A
H 2
E
B
1 A
Path length
I
C
0
F
2
E
0
Now, by examining the destination vertex—
H
—we find that the length of the shortest path
from
A
to
H
is 2. We also find that
H
's predecessor along this shortest path is vertex
E
. From vertex
E
we see that its predecessor is vertex
A
. Thus, the desired shortest path from vertex
A
to vertex
H
is
A
H
. Our algorithm has discovered what we of course knew to be true by inspecting this
simple graph.
→
E
→
