Java Reference
In-Depth Information
T
1
10
3
cost
5
9
5
8
6
0
5
10
9
0123456
2
8
8
6
4
parent
1
2
-1
1
1
1
2
7
5
0123456
0
4
5
(a)
(b)
F
IGURE
29.13
Now vertices
1
and
2
are in set
T
.
Now
T
contains {
1
,
2
}. Vertex
0
is the one in
V-T
with the smallest cost, so add
0
to
T
, as
shown in Figure 29.14 and update the cost and parent for vertices in
V-T
and adjacent to
0
if applicable.
cost[5]
is now updated to
10
and its parent is set to
0
and
cost[6]
is now
updated to
8
and its parent is set to
0
.
T
1
10
3
cost
5
9
5
8
6
0
5
10
10
8
2
0123456
8
8
6
4
parent
1
2
-1
1
1
0
0
2
7
5
0123456
0
4
5
(a)
(b)
F
IGURE
29.14
Now vertices {
1
,
2
,
0
} are in set
T
.
Now
T
contains {
1
,
2
,
0
}. Vertex
6
is the one in
V-T
with the smallest cost, so add
6
to
T
,
as shown in Figure 29.15 and update the cost and parent for vertices in
V-T
and adjacent to
6
if applicable.
1
T
10
3
cost
5
9
5
8
6
0
5
10
10
8
2
0123456
8
8
6
4
parent
1
2
-1
1
1
0
0
5
2
7
0123456
0
4
5
(a)
(b)
F
IGURE
29.15
Now vertices {
1
,
2
,
0
,
6
} are in set
T
.
Search WWH ::
Custom Search