Java Reference
In-Depth Information
FIGURE 28-19
A trace of the traversal in the algorithm to find the cheapest
path from vertex
A
to vertex
H
in a weighted graph
frontVertex
Visited vertex
nextNeighbor
Priority queue (front to back)
5
2
A
D
G
A 0
4
A0
A
empty
2
1
B
B2
A
1
6
B
E
H
D
B
2
A
D5
A
3
3
1
3
E
B2
A
E4
A
D5
A
1
4
B2
A
B
E4
A
D5
A
C
F
I
E
E
3
B
E4
A
D5
A
E3
B
E
E4
A
D5
A
F
E4
A
D5
A
F6
E
H
E4
A
D5
A
F6
E
H9
E
D
5
A
F6
E
H9
E
D5A
D
F6
E
H9
E
G
F
6
E
G7
D
H9
E
F6E
F
G7
D
H9
E
H
G
7D
H 9 E
H
9
F
C
G
7
D
H 9
H
9
C 10
F
E
F
G7D
G
H
9
E
H
9
C
10 F
F
H
H
8G
H
9
H
9
C 10
F
E
F
H8G
H
H 9 E
H 9
F
C 10 F
the edge from
B
to
E
. This total cost is 3. We encapsulate
E
, the cost 3, and the predecessor
B
into
an object that we add to the priority queue. Notice that two objects in the priority queue involve
vertex
E
, but the most recent one has the cheapest path.
We again remove the front entry from the priority queue. The entry contains vertex
E
, so we
visit it and store into
E
the path cost 3 and
E
's predecessor
B
. Vertex
E
has two unvisited neighbors,
F
and
H
. The cost of each path to a neighbor is the cost of the path to
E
plus the weight of the edge
to the neighbor. Two new objects are added to the priority queue.
The next object removed from the priority queue contains the vertex
E
, but since
E
has been
visited, we ignore it. We then remove the next object from the priority queue. The algorithm contin-
ues until the destination vertex
H
is visited.
Figure 28-20 shows the state of the graph at the conclusion of the trace given in Figure 28-19. By
looking at the destination vertex
H
, we can see that the weight of the cheapest path from
A
to
H
is 8.
Tracing back from
H
to
A,
we see that this path is
A
→
D
→
G
→
H
, as we noted in Segment 28.21.
