温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
认清事情的本质！
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(16280)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_084068',
blogTitle:'14、求关键路径',
blogAbstract:'
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list} 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
关键路径习题
下载积分：600
内容提示：关键路径习题——均是精品资料，值得下载！
文档格式：PPT|
浏览次数：50|
上传日期： 07:35:45|
文档星级：
该用户还上传了这些文档
关键路径习题
官方公共微信图的关键路径
(一) AOE网
事件& 含义
v1&&& 开工
活动a1完成，活动a4可以开始
&活动a2完成，活动a5可以开始
活动a3完成，活动a6可以开始
活动a4与a5完成，活动a7和a8可开始,
活动a6完成，活动a9可以开始
活动a7完成，活动a10可以开始
活动a8与a9完成，活动a11可以开始
活动a10和a11完成，整个工程完成
&& 边（弧）：代表活动（操作）；
边权：代表活动的持续时间。记边ak=&i,
j&的权为len(ak)或len(i,j)；
结点：代表事件（状态）。它表示它的各入边代表的活动均已完成，而它的出边代表的活动可以开始。
事实上，某结点代表的事件是它的各入边代表的活动的共同作用结果，同时也是它的各出边代表的活动的启动条件。AOE网中没有入边的结点称为始点，没有出边的结点称为终点。AOE一般用来描述工程进度，结点表示工程进展中的状态，边表示子任务。图
21‑4就是一个AOE网，它可以看作是一个具有11项子任务和9个状态的假想工程的进度图。
(二) AOE网的操作
针对AOE网的操作一般有下列几种:
关键路径CPM(Critical Path Method)。 这种操作最早用于维修与建筑行业中工期进度估算。
&性能估计与复审PERT(Performance Evaluation and Review
Technique)：该项操作最初是为了研制北极星式导弹系统而引入的。
资源分配与多工程调度RAMPS(Resource Allocation&
and& Multi-Project Scheduling)
(三) 关键路径的若干基本概念
下面的阐述中，设AOE网的起点为v0终点为vn.
1．关键路径
AOE网中，从事件i到j的路径中，加权长度最大者称为i到j的关键路径（Critical
Path），记为cp(i,j)。特别地，始点0到终点n的关键路径cp(0,n)是整个AOE的关键路径。
显然，关键路径决定着AOE网的工期，关键路径的长度就是AOE网代表的工程所需的最小工期。
2．事件最早/晚发生时间
事件vi的最早发生时间ve(i)定义为：从始点到vi的最长（加权）路径长度，即cp(0,i)
事件vi的最晚发生时间vl(i)定义为：在不拖延整个工期的条件下，vi的可能的最晚发生时间。即vl(i) = ve(n) -
3．活动最早/晚开始时间
活动ak=&vi,
vj&的最早开始时间e(k)：等于事件vi的最早发生时间，即
e(k) = ve(i) = cp(0, i)
活动ak=&vi,
vj&的最晚开始时间l(k)定义为：在不拖延整个工期的条件下，该活动的允许的最迟开始时间，即
l(k) = vl(j) & len(i, j)
这里，vl(j)是事件j的允许的最晚发生时间，len(i, j)是ak的权。
活动ak的最大可利用时间：定义为l(k)-e(k)
&4．关键活动
若活动ak的最大可利用时间等于0（即(l(k)=e(k)），则称ak 为关键活动，否则为非关键活动。
显然，关键活动的延期，会使整个工程延期。但非关键活动不然，只要它的延期量不超过它的最大可利用时间，就不会影响整个工期。
关键路径的概念，也可以用这里的关键活动定义，即有下面的：
(一) 基本算法
关键路径算法是一种典型的动态规划法，这点在学了后面的算法设计方法后就会看到。下面就来介绍该算法。设图G=(V,
E)是个AOE网，结点编号为1,2,...,n，其中结点1与n 分别为始点和终点，ak=&i,
j&∈E是G的一个活动。
根据前面给出的定义，可推出活动的最早及最晚发生时间的计算方法：
& e(k) = ve(i)
& l(k) = ve(j) -
len(i,j)&&
结点的最早发生时间的计算，需按拓扑次序递推：
&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&
ve(j) = MAX{ ve(i)+len(i, j) }　
对所有&i,j& ∈E的i&
结点的最晚发生时间的计算，需按逆拓扑次序递推：
&&&&&&&&&&&&&
&&&vl(n) =
&&&&&&&&&&&&&&&&
vl(i) = MIN{vl(j) - len(i,
j)}　对所有&i,j&∈E的j&
关于&ve与vl的求法，可参阅图 21‑5。
这种计算方法， 依赖于拓扑排序， 即计算ve( j) 前，应已求得j
的各前趋结点的ve值，而计算vl(i)前，应已求得i的各后继结点的vl值。ve的计算可在拓扑排序过程中进行，即在每输出一个结点i后，在删除i的每个出边&i,j&（即入度减1）的同时，执行
&&&&&&&&&&&&&&&
if ( ve[i]+len(i,j)) & ve[j] )　
&&&&&&&&&&&&&&&
ve[j] = ve[i] + len(i,j)&
实际上，该操作对i的每个后继j分别进行一次。因此对程序作少量扩充即可求得ve。
vl的值可按类似的方法在逆拓扑排序过程（即直接按与拓扑序列相反的次序输出结点的过程）中求得，但一般不必专门这样进行。事实上，通过逆方向使用拓扑序列即可递推出各vl的值，假定拓扑序列是topoSeq，则vl
的值的求法为（结点编号为1~n）。
for (k=1; k&=n; k++) &vl[k] =
ve[n];&& //初始化
for ( k=n; k&=1; k--)
&&&&&&&&&&
i=topoSeq[k];
&&&&&&&&&&
j=（i的第1个出点）;
&&&&&&&&&&
while (j存在)
&&&&&&&&&&&&
(vl[j]-len(i,j)&vl[i])&&&&&
&&&&&&&&&&&&&&&
vl[i]=vl[j]-len(i,j);
&&&&&&&&&&&&
j = （i的下一个出点）;
&&&&&&&&&&
的AOE网的所有事件的最早发生时间ee()；所有事件的最迟发生时间le()；每项活动ai的最早开始时间e()和最迟开始时间l()，完成此工程最少需要多少天？那些是关键活动，是否存在某项活动，当其提高速度后能使整个工程缩短工期?
存储结构及算法设计
1、在结点的定义中增加ee和le 字段用于记录个事件的最早开始时间和最迟开始时间，同时得到关键路径和最小工期
2、邻接矩阵中使用边权代替原来连接标志1
3、进行拓扑排序，形成拓扑序列
1 2 3 4 5 6 7 8 9
4、按拓扑序列顺序，从前向后搜索寻找个活动（即边），若存在该活动，则计算相应事件的最早开始时间。
5、按拓扑序列顺序，从后向前搜索寻找个活动（即边），若存在该活动，则计算相应事件的最迟开始时间。
6、计算各活动的最早开始时间和最迟开始时间
算法源程序：
#include &stdio.h&
#include &stdlib.h&
#define MaxVerNum 20
int visited[MaxVerNum];
typedef char VertexT
typedef struct ArcNode
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
//该弧指向的顶点位置
struct ArcNode *
//指向下一个表结点
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
//权值信息
}ArcN&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
//边结点类型
typedef struct VNode
}VNode, Adjlist[MaxVerNum];
typedef struct
&&&&&&&&&&&
int vernum,
&&&&&&&&&&&&
//顶点数和弧数
//查找符合的数据在数组中的下标
int LocateVer(ALGraph G, char u)
for(i = 0; i & G. i++)
&&&&&&&&&&&&&
if(u == G.vertices[i].data)
&&&&&&&&&&&&&&&&&&&&
if(i == G.vernum)
&&&&&&&&&&&&&
printf("Error u!\n");
&&&&&&&&&&&&&
//常见图的邻接矩阵
void CreateALGraph(ALGraph &G)
int i, j, k,
char v1, v2;
printf("输入顶点数和弧数: ");
scanf("%d %d", &G.vernum,
&G.arcnum);
printf("请输入顶点!\n");
for(i = 0; i & G. i++)
&&&&&&&&&&&&&
printf("请输入第 %d 个顶点: \n", i);
&&&&&&&&&&&&&
fflush(stdin);
&&&&&&&&&&&&&
scanf("%c", &G.vertices[i].data);
&&&&&&&&&&&&&
G.vertices[i].firstarc = NULL;
&&&&&&&&&&&&&
G.vertices[i].indegree = 0;
for(k = 0; k & G. k++)
&&&&&&&&&&&&&
printf("请输入弧的顶点和相应权值(v1, v2, w): \n");
&&&&&&&&&&&&&
//清空输入缓冲区
&&&&&&&&&&&&&
fflush(stdin);
&&&&&&&&&&&&&
scanf("%c %c %d", &v1, &v2,
i = LocateVer(G, v1);
&&&&&&&&&&&&&
j = LocateVer(G, v2);
&&&&&&&&&&&&&
p = (ArcNode *)malloc(sizeof(ArcNode));
&&&&&&&&&&&&&
p-&adjvex =
&&&&&&&&&&&&&
&&&&&&&&&&&&&
p-&nextarc = G.vertices[i].
&&&&&&&&&&&&&
G.vertices[i].firstarc =
&&&&&&&&&&&&&
G.vertices[j].indegree++;&&&&&&&&&&&&&&&&&&
//vi-&vj, vj入度加1
//求图的关键路径函数
void CriticalPath(ALGraph G)
int i, k, e,
int * Ve, * Vl;
//*****************************************
//以下是求时间最早发生时间
//*****************************************
Ve = new int [G.vernum];
Vl = new int [G.vernum];
for(i = 0; i & G.
i++)&&&&&&&&&&&&&
&&&&&&&&&&&&&
Ve[i] = 0;
for(i = 0; i & G. i++)
&&&&&&&&&&&&&
ArcNode * p = G.vertices[i].
&&&&&&&&&&&&&
while(p != NULL)
&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&
if(Ve[i] + p-&info & Ve[k])
&&&&&&&&&&&&&&&&&&&&&&&&&&&
Ve[k] = Ve[i]+p-&
&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&
//*****************************************
//以下是求最迟发生时间
//*****************************************
for(i = 0; i & G. i++)
&&&&&&&&&&&&&
Vl[i] = Ve[G.vernum-1];
for(i = G.vernum-2; i &= 0;
i--)&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&
p = G.vertices[i].
&&&&&&&&&&&&&
while(p != NULL)
&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&
if(Vl[k] - p-&info & Vl[i])
&&&&&&&&&&&&&&&&&&&&&&&&&&&
Vl[i] = Vl[k] - p-&
&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&
//******************************************
for(i = 0; i & G. i++)
&&&&&&&&&&&&&
p = G.vertices[i].
&&&&&&&&&&&&&
while(p != NULL)
&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&
Ve[i];&&&&&&&&&&&&&
//最早开始时间为时间vi的最早发生时间
&&&&&&&&&&&&&&&&&&&&
l = Vl[k] -
p-&&&&&&&&&&&&&
//最迟开始时间
&&&&&&&&&&&&&&&&&&&&
char tag = (e == l) ? '*' : ' '; //关键活动
&&&&&&&&&&&&&&&&&&&&
printf("(%c, %c), e = %2d, l = %2d, %c\n", G.vertices[i].data,
G.vertices[k].data, e, l, tag);
&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&
delete [] Ve;
delete [] Vl;
void main()
ALGraph G;
printf("以下是查找图的关键路径的程序。\n");
CreateALGraph(G);
CriticalPath(G);
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。查看:16698|回复：39
金吾卫大将军
今天的中，我出了关键路径的题，这中类型的题是高级中比较常见的，系统分析师、信息系统项目管理师都是经常出的，网络规划设计师考纲也有项目控制的内容，我看了下大家答题的情况，很多人不了解关键路径和其相关计算的求法，考试出题有关键路径的计算，最早开始时间，最迟开始时间。这里我稍微总结下，当然是应试性质的，要想深入了解，还需多看相关的资料。
(13.08 KB)
在这种AOE网中
最长的一条路径就是关键路径,因为图中每个活动都是必须的，只有最长的工期完成后，项目才真正完成了，图中10+9+20+10 也就是ADFHJ&&，显然是最长的，所以为关键路径。
从左边开始每个活动所需要最长的时间就是最早开始时间，如C，只有A指向它，那么最早开始时间就是5；F，A->C->F
5+4=9，A->D->F 10+9=19,两者比较，后者大，故19为最早开始时间，依次类推。
从右边倒推，可以求的最迟开始时间，如J为49，以I为例，I->J 倒推 49-4=45 所以I最迟开始时间为45；H为例，H->J 倒推49-10=39，H->I->J 倒推 49-4-1=44，两者取最小的，所以H的最迟开始时间为39。
相关练习：
& && && && && && &
& && && && && &&&
有疑问的加我Q ，或者发站短
:lol 看下,知道原理就很简单了
助理工程师
xiexie ,jiang de hen hao
助理工程师
我也来学习学习&&谢谢
谢谢，又明白了一个原理，要是能考这题，应该不会答错了，
& &&&非常感谢
初级工程师
谢谢楼主哈，以前没看过都。学习了:handshake
助理工程师
原来是这样啊，明白了，谢谢楼主！！
学习了,谢谢班主的解释....:lol :lol :lol :lol :lol
领教了哦&&thanks
学习了，谢谢楼主！
楼主是热心人
引用:从右边倒推，可以求的最迟开始时间，如J为49，以I为例，I->J 倒推 49-4=45 所以I最迟开始时间为45；H为例，H->J 倒推49-10=39，H->I->J 倒推 49-4-1=44，两者取最小的，所以H的最迟开始时间为44。 最后数据写错了，两者取最小的，H的最迟开始时间为应为39，而不是44.
金吾卫大将军
引用:原帖由 7277 于
22:24 发表
最后数据写错了，两者取最小的，H的最迟开始时间为应为39，而不是44. 已经改正了，谢谢指正
助理工程师
这是网规的考试内容吧？网工的好像没碰到过这样的题目
助理工程师
谢谢！！！！
一直对关键路径的问题搞不清楚。看了一下还是有点不自信。
高级工程师
多谢斑竹:victory: ，偶天资愚钝先占个位，还是有些没看懂的地方，回家再研究研究。
顺便贴个 AOE网的链接。
助理工程师
先学习了，第一次看到这个原理～
Copyright&
本论坛言论纯属发布者个人意见，不代表51CTO网站立场！如有疑义，请与管理员联系：