Question

哪位大哥帮一下忙。。。。

1.有向图G=(V,E),其中 V(G)={0,1,2,3,4,5}，用<a,b,d>三元组表示弧<a,b>及弧上的权d.E(G)为{<0,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>}，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。
2. 上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为______。
3．AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。
4．在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为______。

Answer 1

第一问就根据题目给的三元组画出有向图
很显然0经过4再到3的路径长度最小，为30+20=50 经过的中间顶点为4

第二问用迪杰斯特拉算法或者prim算法可得 最小生成树为1-2-0-4-3-5，边权之和为75

第三问 aov网中结点表示事件，边表示活动之间的优先关系（边为有向边），aoe网中结点表示事件，边表示活动，边上的权值表示活动的开销。

第四问aoe网中从源点到汇点路径上各活动时间总和最长的路径为关键路径。

希望能帮到你

Answer 2

533123