关键路径详细原理

一、概述

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

我们需要引进两个概念，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);//输出关键路径 
    }
}

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