AOE网G如下所示,求关键路径。(要求标明每个顶点的最早发生时间和最迟发生时间,并画出关键路径)
关键路径:
v0 -> v1 -> v4 -> v5
v0 -> v2 -> v3 -> v5
vi最早发生时间
0 3 2 6 6 8
vi最迟发生时间
e 032668
l 032668
v0 v1 v4 v5
v0 v2 v3 v5
111
v0->v1->v4->v5 / v0->v2->v3->v5
v0:0 v1:3 v2: 2 v3: 6 v4: 6 v5: 8
0 1 2 3 4 5
e 0 3 2 6 6 8
l 0 3 5 6 6 8
关键0145,0235
V0 V1 V2 V3 V4 V5
最早发生时间 0 3 2 6 6 8
最迟发生时间 0 3 5 6 6 8
关键路径 : V0-v1-v4-v5
vo-v2-v3-v5
0145
0235
1
Vi Ve Vl
0 0 0
1 3 3
2 2 2
3 6 6
4 6 6
5 8 8
活动:0-1(0),0-2(2),1-3(1),1-4(0),2-3(0),2-5(3),3-5(0),4-5(0)
关键路径:0145,0235
浮动时间
两条关键路径
0-1-4-5
0-2-3-5
v0,v2,v3,v5
v0,v1,v4,v5;
v0->v1->v3->v5
v0->v2->v3->v5
括扑排序为 0 1 2 3 4 5
ve0=0;ve1=3;ve2=2 ;ve3=2+4=6;ve4 =6 ve5=6+2=8
逆括扑排序 5 4 3 2 1 0
vl5=8; vl4=6 vl3=6 vl2=6-4=2 vl1=6-3=3 v0=0;
关键路径ve与vl值相等
v0->v1->v4->v5
关键路径上的最早和最迟发生时间相同
答案:(1)最早发生时间和最迟发生...
用户登录可进行刷题及查看答案
答案:(1)最早发生时间和最迟发生时间: (2)关键路径:
登录后提交答案