关键路径：完成整个工程所需要的最短时间，这个路径称为关键路径
关键路径上的活动称为关键活动，只有缩短关键活动的工期，才能减少整个工程的工期
ve[j]:事件vj的最早发生时间（max{顶点+边山槐}）
vl[j]:事件vj的最迟发生时间（min{尾-边}）
e[j]：活动aj的最早开始时间（ve(顶点））
v[j]：活动aj的最晚开始时间 （vl（尾）-边）
举个例姿厅子吧：
求上图中VOE网中的关键路径：
1，求事件的最早开始时间ve=max{顶点+边}和最晚开始时间vl=min{尾-边}
2，为了后面更好的求活动的最早开始时间和最晚开始时间，将ve和vl都在图中标识出来，ve用红笔，vl用黑笔
3，逗册友求活动的最早最晚开始时间，最早e={ve顶}，最晚l={vl尾-边}
其中关键活动就是a2,a5,a7,所形成的关键路径就是A->C->D->F
#include <stdio.h>#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <malloc.h>
//事件
struct Event
{
//事件名称
char Name[100]
//是否始发事件
bool IsBegin
//是否终点事件
bool IsEnd
}
//路径
struct Path
{
//出发事件
char FromEventName[100]
//到达事件
char ToEventName[100]
//权重
int Height
}
//输入事件,返回生成的事件数组并通过参数返回事件个斗御仿数
struct Event * CreateEvents(int *OutEventCount)
{
int EventNum = 0
struct Event * ReturnValue = NULL
fflush(stdin)
printf("输入事件总数量(整数) = ")
try
{
scanf("%d",&EventNum)
}
catch(...)
{
printf("输入不正空纤确!")
return NULL
}
*OutEventCount = EventNum
ReturnValue = (struct Event *)malloc(sizeof(struct Event) * EventNum)
memset(ReturnValue,0x0,sizeof(struct Event) * EventNum)
if ( NULL == ReturnValue )
{
printf("分配内存失败!")
return NULL
}
for ( int i = 0 i <EventNum i++ )
{
int TmpInput = 0
printf("输入第[%d]个事件名称 =",i+1)
scanf("%s",ReturnValue[i].Name)
printf("此事拆晌件是否开始事件 (输入0表示否,输入1表示是) =")
scanf("%d",&TmpInput)
if ( TmpInput == 1 )
{
ReturnValue[i].IsBegin = true
}
printf("此事件是否结束事件 (输入0表示否,输入1表示是) =")
scanf("%d",&TmpInput)
if ( TmpInput == 1 )
{
ReturnValue[i].IsEnd = true
}
}
return ReturnValue
}
//销毁事件分配的内存
void DestroyEvents(struct Event **pE)
{
if ( NULL != pE )
{
free(*pE)
}
*pE = NULL
}
//输入路径 返回生成的路径数组,并通过参数返回路径数
struct Path * CreatePathes(int *OutPathCount)
{
struct Path * ReturnValue = NULL
int Count = 0
fflush(stdin)
try
{
while ( true )
{
if ( ReturnValue != NULL )
{
int tmpGoOn = 0
printf("继续添加路径?(输入1继续添加,输入0退出添加路径) = ")
scanf("%d",&tmpGoOn)
if ( 0 == tmpGoOn )
{
break
}
}
else
{
printf("--------------\n")
}
ReturnValue = (struct Path *)realloc(ReturnValue,sizeof(struct Path) * (Count + 1 ))
Count++
printf("输入此路径出发事件名称 = ")
scanf("%s",ReturnValue[Count-1].FromEventName)
printf("输入此路径到达事件名称 = ")
scanf("%s",ReturnValue[Count-1].ToEventName)
printf("输入此路径权重 = ")
scanf("%d",&(ReturnValue[Count-1].Height))
}
}
catch(...)
{
printf("输入不正确!")
return NULL
}
*OutPathCount = Count
return ReturnValue
}
//销毁事件分配的内存
void DestroyPathes(struct Path **pP)
{
if ( NULL != pP )
{
free(*pP)
}
*pP = NULL
}
//递归函数
//计算从当前事件到终点事件的关键路径
//参数:
// const struct Event *pIn_CurrentEvent ---- 当前事件
// const struct Event *pIn_Events ---- 所有事件数组
// const int TotalEventNum ---- 事件总数
// const struct Path *pIn_Pathes ---- 所有路径数组
// const int TotalPathNum ---- 路径总数
// struct Event * pIn_Out_ImportentPaths ---- 用来保存关键路径上的事件数组
// const int ImportPathsNum---- 用来保存关键路径上的事件数组大小
//返回值:
// 从当前事件到终点事件的关键路径权重
int Run(const struct Event *pIn_CurrentEvent,const struct Event *pIn_Events,const int TotalEventNum,const struct Path *pIn_Pathes,const int TotalPathNum,struct Event * pIn_Out_ImportentPaths,const int ImportPathsNum)
{
//1.找到从当前事件出发的所有路径
//2.针对从当前事件出发的所有路径到达的事件分别调用Run看谁返回的权重最大
//3.结束条件:当当前事件为终点事件时结束递归
//结束递归
if ( pIn_CurrentEvent->IsEnd )
{
return 0
}
//找到当前事件出发的所有路径
struct Path *TmpFromThisPathes = (struct Path *)malloc(sizeof(struct Path) * TotalPathNum)
int TmpForThisPathesIndex = 0
if ( NULL == TmpFromThisPathes )
{
printf("递归调用中分配内存失败!")
return 0
}
memset(TmpFromThisPathes,0x0,sizeof(struct Path) * TotalPathNum)
for ( int i = 0 i <TotalPathNum i ++ )
{
if ( strcmp(pIn_Pathes[i].FromEventName,pIn_CurrentEvent->Name) == 0 )
{
memcpy(&(TmpFromThisPathes[TmpForThisPathesIndex]),&(pIn_Pathes[i]),sizeof(struct Path))
TmpForThisPathesIndex++
}
}
//找到当前事件可到达的所有事件 并找到当前路径所有可到达事件中权重最大的
int MaxPower = -1
Event MaxEvent
memset(&MaxEvent,0x0,sizeof(MaxEvent))
for ( int i = 0 i <TmpForThisPathesIndex i++ )
{
for ( int j = 0 j <TotalEventNum j++ )
{
if ( strcmp(pIn_Events[j].Name,TmpFromThisPathes[i].ToEventName) == 0 )
{
//在此对此事件的下一个事件递归调用来得到哪条路径的权重最大
int TmpGotPower = Run(&(pIn_Events[j]),pIn_Events,TotalEventNum,pIn_Pathes,TotalPathNum,pIn_Out_ImportentPaths,ImportPathsNum)
if ( MaxPower <TmpGotPower + TmpFromThisPathes[i].Height )
{
//记录下最大的权重和对应的下个事件
MaxPower = TmpGotPower + TmpFromThisPathes[i].Height
memcpy(&MaxEvent,&(pIn_Events[j]),sizeof(Event))
}
}
}
}
free(TmpFromThisPathes)
TmpFromThisPathes = NULL
//保存关键路径上的事件
if ( MaxEvent.IsEnd )
{
//去掉中间存储的不是关键路径的信息
memset(pIn_Out_ImportentPaths,0x0,ImportPathsNum * sizeof(Event))
}
for ( int i = 0 i <ImportPathsNum i++ )
{
if ( strlen(pIn_Out_ImportentPaths[i].Name) <1 )
{
memset(&(pIn_Out_ImportentPaths[i]),0x0,sizeof(Event))
memcpy(&(pIn_Out_ImportentPaths[i]),&MaxEvent,sizeof(Event))
break
}
}
return MaxPower
}
void main(void)
{
int EventNum = 0
int PathNum = 0
struct Event * pTheEvents = CreateEvents(&EventNum)//获取输入事件
struct Path *pThePathes = CreatePathes(&PathNum)//获取输入路径
if ( NULL == pTheEvents || NULL == pThePathes )
{
goto END_COME_HERE
}
//获取始发点事件 即 IsBegin 为真的事件
struct Event * pTheBeginEvent = NULL
for ( int i = 0 i <EventNum i++ )
{
if ( pTheEvents[i].IsBegin )
{
pTheBeginEvent = pTheEvents + i
break
}
}
if ( NULL == pTheBeginEvent )
{
printf("无始发点事件!\n")
goto END_COME_HERE
}
//定义保存关键路径的数组 EventNum 只是用来表示大小,因为关键路径上的事件个数总不会超过所有事件总数
struct Event *ImportentPaths = (struct Event *)malloc(EventNum * EventNum * sizeof(struct Event))
if ( NULL == ImportentPaths )
{
printf("分配内存失败!\n")
goto END_COME_HERE
}
memset(ImportentPaths,0x0,EventNum * EventNum * sizeof(struct Event))
//递归调用
int TheTotalHeight = Run(pTheBeginEvent,pTheEvents,EventNum,pThePathes,PathNum,ImportentPaths,EventNum)
//因始发事件没有在递归函数中添加到关键路径经过的事件中,所以在此添加.
for ( int i = 0 i <EventNum * EventNum i++ )
{
if ( strlen(ImportentPaths[i].Name) <1 )
{
memset(&(ImportentPaths[i]),0x0,sizeof(Event))
memcpy(&(ImportentPaths[i]),pTheBeginEvent,sizeof(Event))
break
}
}
//输出(说明,因为是递归调用,所以所保存的关键路径上的事件是反序的
printf("已找到,总权重为:%d,关键路径为:\n",TheTotalHeight)
for ( int i = 0 i <EventNum * EventNum i++ )
{
if ( strlen(ImportentPaths[i].Name) <1 )
{
break
}
printf("%s,",ImportentPaths[i].Name)
}
free(ImportentPaths)
ImportentPaths = NULL
END_COME_HERE:
DestroyEvents(&pTheEvents)
DestroyPathes(&pThePathes)
fflush(stdin)
getchar()
}
=========================================
运行结果如下图: ...图片贴不上来,我放到我空间里了:http://hi.baidu.com/moxsone/album/item/1d5fae0f010d9ad2a9645741.html
最短路径只是某一点到闷腊虚另一点走的最快最短的路径，而关键路径以点为事件，需要将所有工程完成时的路径，所以选最长路径为关键路径才能确保所有工程都完成。
设计结果与预测的相符合，关键路径在具体的工程中有着重要的作用，当一个AOE网络中的关键路径只有一条时，加速关键路径上的任一关键活动，能够加速整个工程的完成。
但当一个AOE网络中的关键路径不止一条时，加速任一关键活动不一定能够加速整个工程的完成。 如方案1与方案2在改变关键路径时整个工程的进度没有蚂燃改变。
扩展资料：
关键路径通常（但并非总是）是决定项目工期的进度活动序列。它是项目中最长的路径，即使很小浮动也可能直接影响整个项目的最早完成时间。
关键路径的工期决定了整个项目的工期，任何关键路径上的终端元素的延迟在浮动时间为零或负数时将直接影响项目的预期完成时间（例如在关键路径上没有浮动时间）。 但特殊情况下，如果总浮动时间大于零，则有可能不会局氏影响项目整体进度。
参考资料来源：百度百科-关键路径
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）