Java Reference
In-Depth Information
FIGURE 28-17
A trace of the traversal in the algorithm to find the shortest path
from vertex
A
to vertex
H
in an unweighted graph
nextNeighbor
vertexQueue
frontVertex
Visited vertex
(front to back)
A
A
0
A
0
A
D
empty
G
B
B
B
1
A
D
D
B
1
A
D 1
A
B
E
H
E
E
A
A
E
1
A
B
1
D 1
A
B
1
D 1
A
E
1
A
D 1
A
C
1
A
F
I
E
G
G
G 2
D
E
1
A
E 1
A
G 2
D
F
F
G 2
D
F
2
E
H
H
G 2
D
2
E
H 2
E
F
The length of each path from
A
to these neighbors is 1. Since vertex
A
has no more neighbors, we
remove vertex
B
from the queue. This vertex has vertex
E
as a neighbor, but
E
has been visited
already. This implies that we can get to
E
from
A
without first going through
B
. That is,
B
is not on
any shortest path that begins at
A
and goes through
E
. Indeed, the path
A
→
B
→
E
is longer than
the path
A
→
E
. We do not know whether our final path involves
E
, but if it does, it will not pass
through
B
.
The algorithm now removes vertex
D
from the queue. Its neighbor
G
is unvisited, so we
set
G
's path-length field to 2 and its predecessor to
D
. We then enqueue
G
. The algorithm continues
in this manner and eventually encounters the destination vertex,
H
. After
H
is updated, the outer
loop ends. We then construct the path by working back from
H
, as we did earlier in Segment 28.18.
Question 9
Continue the trace begun in Figure 28-17 to find the shortest path from vertex
A
to
vertex
C
.
28.21
Example.
In a weighted graph, the shortest path is not necessarily the one with the fewest edges.
Rather, it is the one with the smallest edge-weight sum. Figure 28-18a shows a weighted graph
obtained by adding weights to the graph in Figure 28-15a. The possible paths from vertex
A
to ver-
tex
H
are the same as you saw in Figure 28-15b. This time, however, we list each path with its
weight—that is, the sum of the weights of its edges—in Figure 28-18b.
We can see that the smallest path weight is 8, so the shortest path is
A
H
. When
the weights are distances, the term “shortest” is appropriate. When the weights represent costs, we
might think of this path as the “cheapest” path.
→
D
→
G
→