Java Reference
In-Depth Information
figure 14.21
Searching the graph
in the unweighted
shortest-path
computation. The
darkest-shaded
vertices have already
been completely
processed, the
lightest vertices have
not yet been used as
v
,
and the medium-
shaded vertex is the
current vertex,
v
.
The
stages proceed left to
right, top to bottom, as
numbered.
1
V
0
V
1
V
0
V
1
0
0
V
2
V
3
V
4
V
2
V
3
V
4
1
1
2
V
5
V
6
V
5
V
6
1
1
2
2
V
0
V
0
V
1
V
1
0
2
0
2
V
2
V
2
V
3
V
4
V
3
V
4
1
1
3
4
V
5
V
6
V
5
V
6
1
1
2
2
V
0
V
1
V
0
V
1
0
2
0
2
3
3
V
2
V
3
V
4
V
2
V
3
V
4
3
1
1
5
6
V
5
V
6
V
5
V
6
1
1
2
2
V
0
V
1
V
0
V
1
0
2
0
2
3
3
V
2
V
3
V
4
V
2
V
3
V
4
3
3
1
1
7
8
V
5
V
6
V
5
V
6
the total cost of all the iterations is . The first action is more challeng-
ing: We cannot simply scan through the graph table (see Figure 14.4) looking
for an appropriate vertex because each scan could take time and we
need to perform it times. Thus the total cost would be , which is
unacceptable for sparse graphs. Fortunately, this technique is not needed.
When a vertex
w
has its
D
w
lowered from
OE
()
OV
()
V
OV
2
(
)
∞
, it becomes a candidate for
an eyeball visitation at some point in the future. That is, after the eyeball
visits vertices in the current distance group
,
it visits the next distance
group
D
v
+ 1, which is the group containing
w
. Thus
w
just needs to wait in
D
v
Search WWH ::
Custom Search