文档介绍：维普资讯
第卷筇期湘薄大学一然学学报.
年月
求关键路径的一种方法
刘彦
计茸机科学系
【摘要理论和实践出发给出了一种新的求关键路径的方法亚实现它的算法转经典方法简单
不玫变机器空间与时间的数量级
主题词:数据结构:算法:关键略盔:有向图:算潞析
分类号
引言
在一同中经典求关键路径的方法是: 先在拓扑有序前提下求出每个结点事件的
最早发生时间,再按逆拓扑有序求出每个事件的最迟发生时间,接着再根据公
式;一, 其中,】【

种方往有几个缺点、涉及到、、、等太多的因素. 重

的基础上进行的, 且方法相似基本上可使用同一算法, 仅须小量变动. 因而, 求
盼过程可以看成是继求后剀再次重复执行. 本文给出的方法涉及的因素少,
易掌握, 相对而言省时省空间.
理论探讨
定义我们将有向赋权图中人度为零的顶点种为广义源点.
图中和,都是广义源点. 同时, 有向赋权图中广义洱点似个数为时.
该广义源点就是一网中的巩皇.
定义我们将广义源点至某顶点的最乇路径称为孵关键路径. 【为. 而将
长度记为,.特别将广义源点的关键路径记为竹长度为.
图中, 一。。:】, 曰』:
收稿日期:——
维普资讯
彦戈键路径询一砷
。为一。和。
为讨论问题方便起见, 我们先做如下假
设:
设“表示所有以顶点为头的弧的尾顶
点集台.
例图中, 。/。, ,
: , ,表示弧.
上的权即活动持续时间.
, 表示从顶点到顶的弧。
表示某广义源点到顶点“的路径.
定理着中顶点的关键路径均巳知.
则尸“也可求得, 且
【∈『哥某个向赋极胃
“., 。, ⋯.:
由条件: 户.,, ⋯巴知. 于是, ⋯
∥,,“, ⋯.. Ⅳ下
,“反证假设,,由定义及条件可得
“Ⅵ. 当于”不是广义谭点. “中至少包含两个顶点.
中仅包含两个顶点. 即: ,因为。是广义源并且..
所以。』≤≤. 月. 于是
, 一巩,“.“,,⋯.
而,:, ⋯自, . 即. 矛盾.
串至少包含个顶点. 即顷点. 使: ,“易知∈
即啦≤,≤于是的长度跗,,的长度,
而』的长度.≤日一, , ,,⋯
口口,“. 即. 矛盾. 因而”,. 且“
定理设、‘分别为网中的汇点和源点在一网中, 若有递推式
‘。⋯‘,, 自
. ,⋯.成立则孤, “。’。
: , , ⋯为关键活动.
证明首先证存在性.
我们将汇点记为. 由定理的证明过程可知. 存在顶点, 不妨记为.
使。’十【“,,。’.着【不为空. 同样由定理. 可推出.
存在一顶点. 不妨记为¨. 他』,,¨.如此继
: ‘“, .此时. ‘”
为源点. 于是一阿中至少存在一递推式
“, 【, ‘‘,,⋯⋯”
.
下证自⋯, ..⋯”为关键活动
由上面递推式可得
维普资讯
‘。’’‘¨ , 。
, ,¨ . 。