第10章 图

于是从b到a的最短路径为bca，长度4；从b到c的最短路径为bc，长度1；从b到d的最短路径为bcad，长度12；从b到e的最短路径为bce，长度5；从b到f的最短路径为bcf，长度4；从b到g的最短路径为vcfg，长度11。

73.求如图10-56所示PERT图中各结点的最早完成时间、最晚完成时间和缓冲时间以及出关键路径。

解 (1)利用公式TE(vi)?max{TE(vj)??ij}求得各结点的最早完成时间为：

v?Pree(v)jiTE(v1)＝0

TE(v2)＝max{0＋3}＝3 TE(v3)＝max{3＋0，0＋2}＝3 TE(v4)＝max{0＋4，3＋2}＝5 TE(v5)＝max{3＋4，3＋4}＝7 TE(v6)＝max{3＋4，7＋0}＝7 TE(v7)＝max{5＋5，7＋3}＝10 TE(v8)＝max{7＋3，10＋1}＝11 TE(v9)＝max{7＋6，11＋1}＝13

(2)利用公式TL(vi)?vj?Succ(vi)min{TL(vj)??ij}求得各结点的最晚完成时间为：

TL(v9)＝13

TL(v8)＝min{13－1}＝12 TL(v7)＝min{12－1}＝11 TL(v6)＝min{12－3}＝9 TL(v5)＝min{13－6，9－0}＝7 TL(v4)＝min{11－5}＝6

TL(v3)＝min{9－4，6－2，7－4}＝3 TL(v2)＝min{7－4，3－0}＝3 TL(v1)＝min{3－3，3－2，6－4}＝0

(3)利用公式TL(vi)－TE(vi)求得各结点的缓冲时间为：

TS(v1)＝TS(v2)＝TS(v3)＝TS(v5)＝TS(v9)＝0

21

第10章 图

TS(v4)＝6－5＝1 TS(v6)＝9－7＝2 TS(v7)＝11－10＝1 TS(v8)＝12－11＝1

于是，所求关键路径为v1v2v5v9，v1v2v3v5v9。

22