已知有 6 个顶点（顶点编号为 0～5）的有向带权图 G ，其邻接矩阵 A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。

要求：

(1) 写出图 G 的邻接矩阵 A 。

(2) 画出有向带权图 G 。

(3) 求图 G 的关键路径，并计算该关键路径的长度。

邻接矩阵 关键路径

[tag_link]

1）上三角矩阵 A[6][6] 中，第 1 行至第 5 行主对角线上方的元素个数分别为 5, 4, 3, 2, 1,由此可以画出压缩存储数组中的元素所属行的情况，如下图所示。用“平移”的思想，将前 5 个、后 4 个、后 3 个、后 2 个、后 1 个元素，分别移动到矩阵对角线 (“0”) 右边的行上。图 G 的邻接矩阵 A 如下所示。

2）据上面的邻接矩阵，画出有向带权图 G, 如下图所示。

(3) 按照算法，先计算各个事件的最早发生时间，计算过程如下：ve(0)=0;ve(1)=ve(0)+a0→1=4;ve(

2)=max(ve(0)+a0→1,ve(

1)+a1→2)=max(6,4+

5)=9;ve(

3)=ve(

2)+a2→3=9+4=13;ve(

4)=ve(

2)+a2→4=9+3=12;ve(

5)=max(ve(

3)+a3→5,ve(

4)+a4→5)=max(16,1

5)=16;接下来求各个时间的最迟发生时间，计算过程如下：vl(

5)=ve(

5)=16;vl(

4)=vl(

5)−a4→5=16−3=13;vl(

3)=vl(

5)−a3→5=16−3=13;vl(

2)=min(vl(

3)−a2→3,vl(

4)−a2→4)=min(9,10)=9;vl(

1)=vl(

2)−a1→2=4;vl(0)=min(vl(

2)−a0→2,vl(

1)−a0→1)=min(3,0)=0;即 ve() 和 vl() 数组如下表所示。

接下来计算所有活动的最早和最迟发生时间 e() 和 l()：e(a0→1)=e(a0→2)=ve(0)=0;e(a1→2)=ve(1)=4;e(a2→3)=e(a2→4)=ve(2)=9;e(a3→5)=ve(3)=13;e(a4→5)=ve(4)=12;l(a4→5)=vl(5)−a4→5=16−3=13;l(a3→5)=vl(5)−a3→5=16−3=13;l(a2→4)=vl(4)−a2→4=13−3=10;l(a2→3)=vl(3)−a2→3=13−4=9;l(a1→2)=vl(2)−a1→2=9−5=4;l(a0→2)=vl(2)−a0→2=9−6=3;l(a0→1)=vl(1)−a0→1=4−4=0;e() 和 l() 数组与它们的差值如下表所示。

满足 l() - e() = 0 的路径就是关键路径，所以关键路径为a0→1、a1→2、a2→3、a3→5，如下图所示（粗线表示），长度为4+5+4+3=16。