Java Reference
In-Depth Information
figure 14.31
The stages of acyclic
graph algorithm. The
conventions are the
same as those in
Figure 14.21.
0
0
2
2
V
0
V
1
V
0
V
1
4
4
1
3
1
3
10
10
2
2
2
2
V
2
V
3
V
4
V
2
V
3
V
4
5
8
4
6
5
8
4
6
1
1
1
2
V
5
V
6
V
5
V
6
0
0
2
2
2
2
V
0
V
1
V
0
V
1
4
4
1
3
1
3
10
10
1
1
12
2
2
2
2
V
2
V
2
V
3
V
4
V
3
V
4
5
8
4
6
5
8
4
6
1
1
3
4
V
5
V
6
V
5
V
6
0
0
2
2
2
2
V
0
V
1
V
0
V
1
4
4
1
3
1
3
10
10
1
1
3
3
2
2
2
2
V
2
V
3
V
4
V
4
V
2
V
3
5
8
4
6
5
8
4
6
5
5
9
9
1
1
5
6
V
5
V
6
V
5
V
6
0
0
2
2
2
2
V
0
V
1
V
0
V
1
4
4
1
3
1
3
10
10
1
1
3
3
2
2
2
2
V
3
V
4
V
2
V
4
V
2
V
3
5
8
4
6
5
8
4
6
5
5
6
6
1
7
1
8
V
5
V
6
V
5
V
6
at line 32. Immediately we lower
w
's indegree at line 35 and, if it has fallen to
0, we place it on the queue at line 36.
Recall that if the current vertex
v
appears prior to
S
in topological order,
v
must be unreachable from
S
. Consequently, it still has
D
v
≡
∞
Vertices that
appear before
S
in
the topological
order are unreach-
able.
and thus cannot
hope to provide a path to any adjacent vertex
w
. We perform a test at line 38,
and if a path cannot be provided, we do not attempt any distance calculations.
Otherwise, at lines 41 to 45, we use the same calculations as in Dijkstra's
algorithm to update
D
w
if necessary.
Search WWH ::
Custom Search