Java Reference
In-Depth Information
Now
T
contains {
1
,
2
,
0
,
6
}. Vertex
3
or
5
is is the one in
V-T
with the smallest cost. You
may add either
3
or
5
into
T
. Let us add
3
to
T
, as shown in Figure 29.16 and update the cost
and parent for vertices in
V-T
and adjacent to
3
if applicable.
cost[4]
is now updated to
18
and its parent is set to
3
.
T
1
10
3
cost
5
9
5
8
6
0
5
10
18
10
8
2
0123456
8
8
6
4
parent
1
2
-1
1
1
3
0
0
2
7
5
0123456
0
4
5
(a)
(b)
F
IGURE
29.16
Now vertices {
1
,
2
,
0
,
6
,
3
} are in set
T
.
Now
T
contains {
1
,
2
,
0
,
6
,
3
}. Vertex
5
is the one in
V-T
with the smallest cost, so add
5
to
T
, as shown in Figure 29.17 and update the cost and parent for vertices in
V-T
and adjacent
to
5
if applicable.
cost[4]
is now updated to
10
and its parent is set to
5
.
T
1
10
3
cost
5
9
5
8
6
0
5
10
15
108
2
0123456
8
8
6
4
parent
1
2
-1
1
1
5
0
0
5
2
7
0123456
0
4
5
(a)
(b)
F
IGURE
29.17
Now vertices {
1
,
2
,
0
,
6
,
3
,
5
} are in set
T
.
Now
T
contains {
1
,
2
,
0
,
6
,
3
,
5
}. Vertex
4
is the one in
V-T
with the smallest cost, so add
4
to
T
, as shown in Figure 29.18.
As you can see, the algorithm essentially finds all shortest paths from a source ver-
tex, which produces a tree rooted at the source vertex. We call this tree a
single-source
all-shortest-path tree
(or simply a
shortest-path tree
). To model this tree, define a class
named
ShortestPathTree
that extends the
Tree
class, as shown in Figure 29.19.
ShortestPathTree
is defined as an inner class in
WeightedGraph
in lines 200-224
in Listing 29.2.
The
getShortestPath(int sourceVertex)
method was implemented in lines 156-197
in Listing 29.2. The method sets
cost[sourceVertex]
to
0
(line 162) and
cost[v]
to
shortest-path tree
Search WWH ::
Custom Search