已知有6个顶点(项点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。
问答题
写出图G的邻接矩阵A。
【正确答案】正确答案：由数组得图G的邻接矩阵A如下图所示。
【答案解析】
问答题
画出有向带权图G。
【正确答案】正确答案：根据上面的邻接矩阵，画出有向带权图G，如下图所示。
【答案解析】
问答题
求图G的关键路径，并计算该关键路径的长度。
【正确答案】正确答案：按照算法，先计算各个事件的最早发生时间，计算过程如下： ve(0)=0； ve(1)=ve(0)+a
0→1
=4； ve(2)=max{ve(0))+a
0→1
，ve(1)+a
1→2
}=max(6，4+5)=9； ve(3)=ve(2)+a
2→3
=9+4=13； ve(4)=ve(2)+a
2→4
=9+3=12； ve(5)=max{ve(3)+a
3→5
，ve(4)+a
4→5
}=max(16，15：)=16； 接下来求各个时间的最迟发生时间，计算过程如下： vl(5)=ve(5)=16； vl(4)=vl(5)-a
4→5
=16-3=13； vl(3)=vl(5)-a
3→5
=16-3=13； vl(2)=min{vl(3)-a
2→3
，vl(4)-a
2→4
}=min(9，10)=9； vl(1)=vl(2)-a
1→2
=4； v1(0)=min{vl(2)-a
0→2
，Vl(1)-a
0→1
}=min(3，0)； 即ve()和vl()数组如下表所示：
接下来计算所有活动的最早和最迟发生时间e()和l()： e(a
0→1
)=e(a
0→2
)=ve(0)=0； e(a
1→2
)ve(1)=4； e(a
2→3
)=e(a
2→4
)=ve(2)=9； e(a
3→5
)-ve(3)=13； e(a
4→5
)=ve(4)=12； l(a
4→5
)=vl(5)-a
4→5
=16-3=13； l(a
3→5
)=vl(5)-a
3→5
=16-3=13； l(a
2→4
)=vl(4)a
2→4
=13-3=10； l(a
2→3
)-vl(3)-a=
2→3
13-4=9； l(a
1→2
)=vl(2)-a
1→2
=9-5=4： l(a
0→2
)=vl(2)-a
0→2
=9-6=3； l(a
0→1
)=vl(1)-a
0→1
=4-4=0； e()和l()数组与它们的差值如下表所示：
满足l()-e()=0的路径就是关键路径，所以关键路径为a
0-＞1
、a
1-＞2
、a
2-＞3
、a
3-＞5
，如下图所示(粗线表示)。
接下来计算所有活动的最早和最迟发生时间e()和l()： e(a
0→1
)=e(a
0→2
)=ve(0)=0； e(a
1→2
)ve(1)=4； e(a
2→3
)=e(a
2→4
)=ve(2)=9； e(a
3→5
)-ve(3)=13； e(a
4→5
)=ve(4)=12； l(a
4→5
)=vl(5)-a
4→5
=16-3=13； l(a
3→5
)=vl(5)-a
3→5
=16-3=13； l(a
2→4
)=vl(4)a
2→4
=13-3=10； l(a
2→3
)-vl(3)-a=
2→3
13-4=9； l(a
1→2
)=vl(2)-a
1→2
=9-5=4： l(a
0→2
)=vl(2)-a
0→2
=9-6=3； l(a
0→1
)=vl(1)-a
0→1
=4-4=0； e()和l()数组与它们的差值如下表所示：
满足l()-e()=0的路径就是关键路径，所以关键路径为a
0-＞1
、a
1-＞2
、a
2-＞3
、a
3-＞5
，如下图所示(粗线表示)。
【答案解析】