欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

关键路径详细原理

程序员文章站 2024-03-24 14:26:04
...

一、概述

  关键路径,顾名思义,就是一个程序中最关键的路径,它关系到整个程序的时间进度,而关键二字指临界点。

我们需要引进两个概念,AOE和AOV网。

二、AOE和AOV网

  AOE和AOV网都是一个大型程序的示意图。而AOV关注事件,AOE网关注时间。

  举个例子:我需要写一篇博客,在脑回路清奇的我来看,应该具有以下步骤。首先写之前你的明白自己写什么吧(设定目标),然后你得有主干知识编写的同时,还得润色自己的语言,如果同时再举一个形象的例子(例如这一段)就好了,之后再代码展示一下的同时进行注释,最后看看没什么问题就可以发布了。

关键路径详细原理

 

  我们发现一个问题,例如在第三步上完成主干知识耗时过多,虽然选取例子和润色语言很快完成,但是主干知识却拖垮了整个工程的进度,当它们全部完成时,才能进入下一环节,所以它是一个关键点。所以对这一工程来说关键点有开始博客,选取对象,主干知识,代码展示,完成博客。然而,开始博客-->选取对象-->主干知识-->代码展示-->完成博客,这一条路径被称为关键路径。它对一些AOE问题具有非常重要的作用。(1)完成工期需要多少时间 (2)那些工程是影响工程进度的关键 (3)求实际耗时的关键路径。

三、关键路径算法

1)首先我们需要定义一些元素,这在写程序的时候会用到:

最早开始时间(Earliest Start),是指某项活动能够开始的最早时间,只决定于项目计划,只要计划的条件满足了就可以开始的时间。

最迟开始时间(Latest Start),是指为了使项目在要求完工时间内完成,某项活动必须开始的最迟时间。

最早结束时间(Earliest Finish),是指某项活动能够完成的最早时间。

最迟结束时间(Latest Finish),是指为了使项目在要求完工时间内完成,某项活动必须完成的最迟时间。

根据最早开始时间和最晚开始时间,可以判断它是否为关键路径。

我们需要理解一下两点:

【1】求事件最早发生的过程时间的过程为从头到尾找拓扑序列的过程。

【2】再求关键路径之前,先调用拓扑排序算法代码来计算顶点最早发生时间与拓扑序列表。

2)我们来分析一下数据的存储结构:

我们肯需要定义以下内容:

入度 in、本身数据 data、边 edge、邻接域 adjvex、过程的耗时(权值) weight。

3)现在我们假如要解决以下图:

关键路径详细原理

我们可以使用这样的邻接表存图:

 关键路径详细原理

四、代码实现

数组etv存储事件最早发生时间,数组ltv存储事件最迟发生时间。
ve 是指从始点开始到顶点Vj的最大路径长度
vl 是指在不推迟整个工期的前提下,事件vj允许的最晚发生时间
ee 若活动ai由弧<vk,vj>表示,则活动ai的最早开始时间应该等于事件vk的最早发生时间
el 若活动ai由弧<vk,vj>表示,则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后

 

用以存图的主函数:

int main() 
{
    scanf("%d%d", &n, &m);
    memset(mp, inf, sizeof(mp));//将未联通的点初始为最大值 
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[i] = {u, v, w};
        mp[u][v] = w;
        into[v]++;//入度增加 
    }
    solve();

    return 0;
} 

拓扑求最大路径:

void topo()//拓扑求最大路径 
{
    int cnt = 0;//栈顶指针为零 
    for(int i = 1; i <= n; i++) //数次寻找 
	{
        int k=-1;
        for(int j=1;j<= n; j++) 
		{
            if(into[j]==0)//如果入度为0,可以进栈了 
			{
                Stack[++cnt] = j;
                k = j;
                into[j] = -1;
                break;//如果有为零的就可以立刻结束 
            }
        }
        for(int j = 1; j <= n; j++) 
		{
            if(mp[k][j] != inf)//假如联通 
			{
                ve[j] = max(ve[j], ve[k] + mp[k][j]);//找到最大路径 
                into[j]--;//入度减一 
            }
        }
    }
}

关键路径

void solve() {
    topo();
    memset(vl, inf, sizeof(vl));//最晚发生时间初始为最大 
    vl[Stack[n]] = ve[Stack[n]];//最晚等于最大路径 
    for(int i = n; i >= 1; i--) //从后向前找 
	{
        for(int j = 1; j <= n; j++)
		 {
            if(mp[Stack[i]][j] != inf) //如果两点之间有联系 
			{
                vl[Stack[i]] = min(vl[j] - mp[Stack[i]][j], vl[Stack[i]]);//更新最晚时间 
            }
        }
    }
    for(int i = 1; i <= m; i++) //计算ee
	{
        ee[i] = ve[e[i].u];
    }

    for(int i = 1; i <= m; i++)//计算el
	{
        el[i] = vl[e[i].v] - e[i].w;
    }
    printf("\n");
    for(int i = 1; i <= m; i++) 
	{
        if(ee[i] == el[i]) printf("%d %d %d\n", e[i].u, e[i].v, e[i].w);//输出关键路径 
    }
}


    多看看,多理解,实在不行代数模拟一下,你就会理解这个比较困难的东西。