Java Reference
In-Depth Information
figure 14.34
An event-node graph
C
3
0
0
0
0
F
3
2
4
7d
7
0
0
A
3
D
2
H
1
G
2
0
1
6d
6
8d
8
10d
10
B
2
0
0
E
1
K
4
3
5
9
the possibility of a
positive-cost cycle,
which is equivalent to a negative-cost
cycle in shortest-path problems. If any positive-cost cycles are present, we
could ask for the longest simple path. However, no satisfactory solution is
known for this problem. Fortunately, the event-node graph is acyclic; thus we
need not worry about cycles. We can easily adapt the shortest-path algorithm
to compute the earliest completion time for all nodes in the graph. If
EC
i
is
the earliest completion time for node
i
,
the applicable rules are
Edges show which
activity must be
completed to
advance from one
vertex to the next.
The earliest com-
pletion time is the
longest path.
EC
1
= 0
and
EC
w
= Max
(
v, w
) ∈
E
(
EC
v
+
c
v, w
)
Figure 14.35 shows the earliest completion time for each event in our exam-
ple event-node graph. We can also compute the latest time,
LC
i
,
that each event
can finish without affecting final completion time. The formulas to do this are
The latest time an
event can finish
without delaying
the project is also
easily computable.
LC
N
=
EC
N
and
LC
v
= Min
(
v, w
) ∈
E
(
LC
w
-
c
v, w
)
These values can be computed in linear time by maintaining for each vertex a
list of all adjacent and preceding vertices. The earliest completion times are
computed for vertices by their topological order, and the latest completion
times are computed by reverse topological order. The latest completion times
are shown in Figure 14.36.
figure 14.35
Earliest completion
times
3
6
6
9
C
3
0
0
0
0
F
3
2
4
7d
7
0
0
0
3
5
5
7
9
10
A
3
D
2
G
2
0
H
1
1
6d
6
8d
8
10d
10
B
2
2
3
7
0
0
E
1
K
4
3
5
9
Search WWH ::
Custom Search