已知有向无环图G的顶点集合为{1, 2, 3, 4, 5, 6},弧集为{(1, 2), (1, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 6), (5, 6)},各弧的持续时间分别为{1, 2, 3, 4, 5, 6, 7, 8}。若事件v1的发生时间为0,则事件v5的最迟发生时间为:

答案解析

**A错误:**从v5到v1的最短路径为v5->v2->v1,长度为4+1=5。 **B正确:**从v5到v1的最短路径为v5->v3->v1,长度为6+5=11。因此,v5的最迟发生时间为v1的发生时间+最短路径长度,即0+11=11。 **C错误:**从v5到v1的最短路径为v5->v4->v2->v1,长度为7+3+1=11。 **D错误:**从v5到v1的最短路径为v5->v4->v3->v1,长度为7+5+5=17。
正确答案:B
随机推荐
开始刷题