精华内容
下载资源
问答
  • 关键路径

    千次阅读 多人点赞 2017-02-28 10:41:47
    关键路径

    AOE网:在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,我们称之为AOE网(Activity On Edge Network)。

    如下图所示:



    AOV网与AOE网的比较

    下面是AOV网


    下面是AOE网



    下面介绍几个名词解释:

    etv(Earliest Time Of Vertex):事件最早发生时间,就是顶点的最早发生时间;
    ltv(Latest Time Of Vertex):事件最晚发生时间,就是每个顶点对应的事件最晚需要开始的时间,如果超出此时间将会延误整个工期。
    ete(Earliest Time Of Edge):活动的最早开工时间,就是弧的最早发生时间。
    lte(Latest Time Of Edge):活动的最晚发生时间,就是不推迟工期的最晚开工时间。

    所以可以知道:


    此图的etv和ltv和ete和lte

    如下图:



    由此,可以做出他的邻接表,如下所示:


    所以可以得出他的关键路径:


    代码如下:

    // 边表结点声明
    typedef struct EdgeNode
    {
    	int adjvex;
    	struct EdgeNode *next;
    }EdgeNode;
    
    // 顶点表结点声明
    typedef struct VertexNode
    {
    	int in;			// 顶点入度
    	int data;
    	EdgeNode *firstedge;
    }VertexNode, AdjList[MAXVEX];
    
    typedef struct
    {
    	AdjList adjList;
    	int numVertexes, numEdges;
    }graphAdjList, *GraphAdjList;
    
    int *etv, *ltv;
    int *stack2;			// 用于存储拓扑序列的栈
    int top2;				// 用于stack2的栈顶指针
    
    // 拓扑排序算法
    // 若GL无回路,则输出拓扑排序序列并返回OK,否则返回ERROR
    Status TopologicalSort(GraphAdjList GL)
    {
    	EdgeNode *e;
    	int i, k, gettop;
    	int top = 0;		// 用于栈指针下标索引
    	int count = 0;		// 用于统计输出顶点的个数
    	int *stack;			// 用于存储入度为0的顶点
    	
    	stack = (int *)malloc(GL->numVertexes * sizeof(int));
    	
    	for( i=0; i < GL->numVertexes; i++ )
    	{
    		if( 0 == GL->adjList[i].in )
    		{
    			stack[++top] = i;	// 将度为0的顶点下标入栈
    		}
    	}
    	
    	// 初始化etv都为0
    	top2 = 0;
    	etv = (int *)malloc(GL->numVertexes*sizeof(int));
    	for( i=0; i < GL->numVertexes; i++ )
    	{
    		etv[i] = 0;
    	}
    	stack2 = (int *)malloc(GL->numVertexes*sizeof(int));
    	
    	while( 0 != top )
    	{
    		gettop = stack[top--];		// 出栈
    		// printf("%d -> ", GL->adjList[gettop].data); 
    		stack2[++top2] = gettop;	// 保存拓扑序列顺序 C1 C2 C3 C4 .... C9
    		count++;				
    		
    		for( e=GL->adjList[gettop].firstedge; e; e=e->next )
    		{
    			k = e->adjvex;
    			// 注意:下边这个if条件是分析整个程序的要点!
    			// 将k号顶点邻接点的入度-1,因为他的前驱已经消除
    			// 接着判断-1后入度是否为0,如果为0则也入栈
    			if( !(--GL->adjList[k].in) )	
    			{
    				stack[++top] = k;
    			}
    			
    			if( (etv[gettop]+e->weight) > etv[k] )
    			{
    				etv[k] = etv[gettop] + e->weight;
    			}
    		}
    	}
    	
    	if( count < GL->numVertexes )	// 如果count小于顶点数,说明存在环
    	{
    		return ERROR;
    	}
    	else
    	{
    		return OK;
    	}
    }
    
    // 求关键路径,GL为有向图,输出GL的各项关键活动
    void CriticalPath(GraphAdjList GL)
    {
    	EdgeNode *e;
    	int i, gettop, k, j;
    	int ete, lte;
    	
    	// 调用改进后的拓扑排序,求出etv和stack2的值
    	TopologicalSort(GL);
    	
    	// 初始化ltv都为汇点的时间
    	ltv = (int *)malloc(GL->numVertexes*sizeof(int));
    	for( i=0; i < GL->numVertexes; i++ )
    	{
    		ltv[i] = etv[GL->numVertexes-1];
    	}
    	
    	// 从汇点倒过来逐个计算ltv
    	while( 0 != top2 )
    	{
    		gettop = stack2[top2--];	// 注意,第一个出栈是汇点
    		for( e=GL->adjList[gettop].firstedge; e; e=e->next )
    		{
    			k = e->adjvex;
    			if( (ltv[k] - e->weight) < ltv[gettop] )
    			{
    				ltv[gettop] = ltv[k] - e->weight;
    			}
    		}
    	}
    	
    	// 通过etv和ltv求ete和lte
    	for( j=0; j < GL->numVertexes; j++ )
    	{
    		for( e=GL->adjList[j].firstedge; e; e=e->next )
    		{
    			k = e->adjvex;
    			ete = etv[j];
    			lte = ltv[k] - e->weight;
    			
    			if( ete == lte )
    			{
    				printf("<v%d,v%d> length: %d , ", GL->adjList[j].data, GL->adjList[k].data, e->weight );
    			}
    		}
    	}
    }


    展开全文
  • AOE网中为什么关键路径是最长路径

    千次阅读 2018-03-08 19:25:20
    AOE网中为什么关键路径是最长路径 我开始也对AOE网中的关键路径很懵,不明白为什么关键路径就是最长路径,难道不应该是最短路径吗 今天又看了一下相关的知识点,发现还是对基础掌握不够牢固。 需要明确的是,AOE...

    AOE网中为什么关键路径是最长路径

    我开始也对AOE网中的关键路径很懵,不明白为什么关键路径就是最长路径,难道不应该是最短路径吗

    今天又看了一下相关的知识点,发现还是对基础掌握不够牢固。
    需要明确的是,AOE网中,顶点被称为事件,而边(或弧)才是活动的描述,边的权值代表活动所花费的时间,因此,事件就是一个活动结束,另一个活动开始的标志,那么要完成整项工程就需要将前面的活动全部完成,所以选最长的路径作为关键路径才能确保工程被完成。

    而最短路径只是一个点到另一个点之间走的最短最快的路径

    又比如说求一个事件的最早发生时间,其实是一个道理,假如事件j的最早发生时间为ve(j),那么也就是说j事件要想发生,就必须执行完全部的入度事件,因此,就是从源点到j点的最长路径长度

    换种说法,设ve(j)为j事件的最早开始时间,vl(i)为j的最迟开始时间,那么关键路径就是ve(j)=vl(j)的路径

    展开全文
  • 关键路径求解

    千次阅读 2018-07-15 10:29:01
    前言:首先关键路径是针对DAG图来说的,我们通常用AOE网来表示一个工程的进行过程,AOV网可以转换为AOE网,AOE网是没有环的,通常关键路径求解需要弄清楚以下四个概念:事件最早发生时间Ve[u]、事件最晚发生时间Vl[u...

    前言:首先关键路径是针对DAG图来说的,我们通常用AOE网来表示一个工程的进行过程,AOV网可以转换为AOE网,AOE网是没有环的,通常关键路径求解需要弄清楚以下四个概念:

    事件最早发生时间Ve[u]、事件最晚发生时间Vl[u]

    活动最早发生时间e[r]、活动最晚发生时间l[r]

    在AOE网(Activity On Edge,用带权的边表示活动,用顶点表示事件的有向图)中,【其实一个事件(顶点)仅表示一个中介状态】首先,我们要求出每个事件(顶点)的最早发生时间Ve[u]和最晚发生时间Vl[u],“事件最早发生时间”可用拓扑排序来进行求解;而事件的最晚发生时间可以用逆拓扑来求解。以上两个求解出来后,就可以计算活动最早发生时间e[r]和活动最晚发生时间l[r]了,他们的关系如下:

    e[r]=Ve[u]

    l[r]+length[r]=Vl[v]

    代码如下:

    #include"stdafx.h"
    #include<cstdio>
    #include<stack>
    #include<algorithm>
    #include<cmath>
    #include<iostream>
    #include<vector>
    #include<queue>
    using namespace std;
    const int maxn = 500;
    int Vertexnum, Edgenum;
    struct node {
    	int v;
    	int weight;
    };
    vector<node> adj[maxn];//邻接表存储DAG图
    int innode[maxn] = { 0 };//记录每个结点的入度
    queue<int> q;
    stack<int> s;//运用一个栈,到时候实现逆拓扑
    int Ve[maxn];//事件发生的最早时间
    int Vl[maxn];//事件发生的最晚时间
    bool topologicalsort() {//拓扑排序
    	for (int i = 0; i < Vertexnum; i++) {//将所有入度为0的点加入到队列中
    		if (innode[i]==0) {
    			q.push(i);
    		}
    	}
    	while (!q.empty()) {
    		int u = q.front();//取队首元素
    		q.pop();
    		s.push(u);//进入栈
    		for (int i = 0; i < adj[u].size(); i++) {//进行入度更新操作
    			int v = adj[u][i].v;
    			innode[v]--;
    			if (innode[v] == 0) {//如果入度为0的点,则入队
    				q.push(v);
    			}
    			if (Ve[u] + adj[u][i].weight > Ve[v]) {//计算事件最早发生时间
    				Ve[v] = Ve[u] + adj[u][i].weight;
    			}
    		}
    	}
    	if (s.size() == Vertexnum) return true;
    	else return false;//否则拓扑失败,说明此图是存在环,不是DAG图
    }
    void antitopologicalsort() {//逆拓扑求事件最晚发生时间
    	while (!s.empty()) {
    		int u = s.top();
    		s.pop();
    		for (int i = 0; i < adj[u].size(); i++) {//计算事件最晚发生时间
    			int v = adj[u][i].v;
    			if (Vl[v] - adj[u][i].weight<Vl[u]) {
    				Vl[u] = Vl[v] - adj[u][i].weight;
    			}
    		}
    	}
    }
    void criticalpath() {//关键路径
    	fill(Ve, Ve + maxn, 0);//事件最早发生时间初始化
    	if (topologicalsort() == false) return;//拓扑失败
    	fill(Vl, Vl + maxn, Ve[Vertexnum - 1]);//事件最晚发生时间初始化
    	antitopologicalsort();
    	cout << "关键路径长度:" << Ve[Vertexnum - 1] << "\n";//输出关键路径长度
    	for (int u = 0; u < Vertexnum; u++) {//遍历所有的边
    		for (int i = 0; i < adj[u].size(); i++) {
    			int v = adj[u][i].v;//边的两个端点分别是u和v
    			int e = Ve[u];//活动最早发生时间
    			int l = Vl[v] - adj[u][i].weight;//活动最晚发生时间
    			if (e == l) {
    				cout << u << "->" << v << "\n";//输出关键路径
    			}
    		}
    	}
    }
    int main() {
    	cin >> Vertexnum >> Edgenum;
    	int start, end, weight;
    	for (int i = 0; i < Edgenum; i++) {
    		cin >> start >> end >> weight;
    		node N;
    		N.v = end;
    		N.weight = weight;
    		innode[end]++;//入度加1
    		adj[start].push_back(N);
    	}
    	criticalpath();//关键路径
    	return 0;
    }

    运行结果如下:



        补充:其实求AOE网中的关键路径就是求DAG最长路路径,所以对于以上求DAG最长路还有一种更简单的办法:利用动态规划思想去解决,令dp[i]表示以i为源点的最长路,如果要求dp[i],就必须求出以源点i出发能够到达的顶点j的dp[j],而dp[j]的求解又是一样的思路,其中DAG图中出度为0的点v,他的dp[v]就是为0了,很显然,求解dp数组可以利用递归去求解。当求出所有的dp[i],其中dp值最大的就是DAG图的最长路径长度,代码如下:

    以下算法实现的功能是:求出最长路径长度和输出最长路径序列

    #include"stdafx.h"
    #include<cstdio>
    #include<stack>
    #include<algorithm>
    #include<cmath>
    #include<iostream>
    #include<vector>
    #include<queue>
    using namespace std;
    const int maxn = 500;
    int Vertexnum, Edgenum;
    struct node {
    	int v;
    	int weight;
    };
    vector<node> adj[maxn];//邻接表存储DAG图
    int outnode[maxn] = { 0 };//记录每个顶点的出度
    int dp[maxn];
    void init() {//dp数组初始化
    	fill(dp, dp + maxn, -1);
    	for (int i = 0; i < Vertexnum; i++) {
    		if (outnode[i] == 0) {//初始化出度为0的dp为0
    			dp[i] = 0;
    		}
    	}
    }
    vector<int> sumpath[maxn];//sumpath[i]数组表示:以i为源点的DAG最长路路径序列
    int path[maxn];//存放DAG最长路路径序列
    int DFS(int index) {//递归求解dp数组
    	if (dp[index] == 0) return dp[index];//到达递归边界
    	for (int i = 0; i < adj[index].size(); i++) {
    		int v = adj[index][i].v;
    		int weight = adj[index][i].weight;
    		int distv = DFS(v);
    		if (dp[index] < distv + weight) {
    			dp[index] = distv + weight;
    			path[index] = v;//顶点index的后继结点是v(和Dijkstra算法记录前驱结点的思路差不多)
    		}
    	}
    	return dp[index];
    }
    int main() {
    	cin >> Vertexnum >> Edgenum;
    	int start, end, weight;
    	for (int i = 0; i < Edgenum; i++) {
    		cin >> start >> end >> weight;
    		node N;
    		N.v = end;
    		N.weight = weight;
    		outnode[start]++;//更新结点的出度
    		adj[start].push_back(N);
    	}
    	init();//初始化
    	for (int i = 0; i < Vertexnum; i++) {
    		path[i] = i;//初始化每个结点的后继结点为自身
    	}
    	int maxdp = -1;//记录最大的dp[i]的值
    	int longestindex;//表示DAG最长路路径是以longestindex为源点
    	for (int i = 0; i < Vertexnum; i++) {
    		int temp = DFS(i);
    		sumpath[i].push_back(i);
    		int j = i;
    		while (path[j] != j) {
    			j = path[j];
    			sumpath[i].push_back(j);
    		}
    		if (maxdp < temp) {
    			maxdp = temp;
    			longestindex = i;
    		}
    	}
    	cout << "关键路径长度:" << maxdp << "\n";
    	cout << "关键路径序列为:";
    	for (int i = 0; i < sumpath[longestindex].size(); i++) {//输出以longestindex为源点的DAG最长路
    		cout << sumpath[longestindex][i];
    	}
    	return 0;
    }

    运行结果如下:



    展开全文
  • 关键路径的计算

    千次阅读 多人点赞 2014-06-21 09:46:46
    从源点到汇点路径长度最长的路径为该工程的关键路径,即关键路径可以保证所有路径的活动都能够完成。 ok,再次进入我们的作业题: 如下图所示的AOE网(弧上权值代表活动的持续天数) 1)完成此工程最少所需要...

              从源点到汇点路径长度最长的路径为该工程的关键路径,即关键路径可以保证所有路径的活动都能够完成。

          ok,再次进入我们的作业题:

          如下图所示的AOE网(弧上权值代表活动的持续天数)

               1)完成此工程最少所需要多少天?
               2)哪些是关键活动,在图中表示出关键路径

            

         我们先计算最早发生时间ve和最迟发生时间vl:

     

      1 2 3 4 5 6 7 8 9 10
    Ve 0 5 6 12 15 16 16 19 21 23
    Vl 0 9 6 12 15 21 16 19 21 23


         首先呢,编号1和编号10分别为该工程的源点和汇点,我们规定最早发生时间ve(源点)=0,最迟发生时间vl(汇点)=ve(汇点)。那么这两个量该如何计算呢,看图:


         对于事件i来说,ve(i) = Max{ve(m) + dut(<m, i>)},vl(i) = Min{vl(j) – dut(<i, j>)};其中ve(m)代表i前一个事件的最早发生时间,dut(<m, i>)表示从m到i的持续时间,大家可以把它看成一个递归算法,一直调用ve(),直到ve(源点)为止,然后取其最大值,因为它要保证所有路径上的活动都能完成;而最迟发生时间和前者一样,一直递归调用vl(),直到vl(汇点)为止,然后取其最小值即可。

        回到原题中对照例图可以很快地得到表格所示内容。

        我们再来看两个概念:e(i)和l(i),前者为活动ai 的最早可能开始时间,后者为活动ai的最迟允许开始时间。区别于前边的ve和vl,e和l为标识的是某活动的时间,而前者是某事件的时间。

        假如从事件m到事件i的活动为af,则有e(f)=ve(m), l(f)=vl(i)–dut(<m,i>) ,即活动af的最早可能开始时间为其弧尾事件最早可能发生时间;最迟允许开始时间为其弧尾事件最迟发生时间与两个事件的持续时间之差。是不是感觉有点别扭,但只要理解了这几个关键词也就很容易看懂了。于是乎 e(k) = l(k)的活动就是关键活动 ,请看图表:

     

      a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13
    5 6 3 6 3 3 4 1 4 5 2 4 2
    e 0 0 5 6 6 12 12 15 15 16 19 16 21
    l 4 0 9 6 12 12 17 15 15 16 19 21 21


         由图和前边计算的ve和vl可以得到各活动的e和l,如上表所示,则关键活动为a2,a4,a6,a8,a9,a10,a11和a13,所以完成该工程至少需要的天数d=6+6+3+1(4)+5(2)+2=23,该工程的关键路径有两条,即1->3->4->5->7->9->10和1->3->4->5->8->9->10。

    更新:6号节点的最迟发生时间vl应该是19 而不是21。。。

     

    展开全文
  • 文章目录一,什么是关键路径二,求解关键路径需要的4个描述量三,如何求得关键路径 视频参考:6.6.4关键路径2–求解关键路径 一,什么是关键路径 【引例 1】某项目的任务是对A公司的办公室重新进行装修 如果10月1日...
  • 关键路径讲解

    2020-11-14 21:47:10
    关键路径详解 最近数据结构刚刚学到关键路径这里,老师为了赶进度开始讲的飞快,可能上课一不留神就会跟不上老师的思路与节奏,只好课下自己学习一下关键路径,这里给他做一个总结,也算是自己的一种记录。 这是一...
  • 构造PERT图,需要明确四个概念:事件、活动、松弛时间和关键路线。1、事件(Events)表示主要活动结束的那一点;2、活动(Activities)表示从一个事件到另一个事件之间的过程;3、松弛时间(slack t...
  • 图之关键路径

    千次阅读 2016-11-23 21:00:40
    图之关键路径
  • 项目关键路径

    千次阅读 2016-06-23 17:53:42
    项目关键路径 项目关键路径,在项目管理中,关键路径是指网络终端元素的元素的序列,该序列具有最长的总工期并决定了整个项目的最短完成时间。关键路径的工期决定了整个项目的工期。任何关键路径上的终端元素的延迟...
  • 在学习数据结构的过程中,我发现关键路径的中的概念取名使得第一印象让人容易产生误解,所以我用最通俗易懂的例子来解释解释这些概念的实际含义。 基本概念——AOE网 有几个最基本的概念我们要先了解,在带权有向图...
  • 图——关键路径

    万次阅读 多人点赞 2019-04-02 09:10:27
    AOE网:在一个表示工程的带权有向图中,用顶点表示事件(如V0),用有向边表示活动(如<v0,v1> = a1),边上的权值表示活动的持续时间,称这样的有向图为边表示的活动的网,简称AOE网(activity on edge ...
  • 关键路径求法

    万次阅读 2018-03-26 13:15:05
    关键路径概念: 在无回路的有向网络中,假设只有一个入度为0的顶点(称为源点)和一个出度为0的顶点(称为汇点),则从源点到汇点之间的最长的路径称为关键路径。AOE网: 无回路有向网络可以用来表示一个包含多项活动的...
  • 图解:什么是关键路径

    千次阅读 多人点赞 2020-05-06 20:31:39
    小禹禹,五一假期马上结束了,你们过得怎么样呢?有没有玩得很开心,收获满满呢?好想听你们在评论区说一说。哈哈,不过我们还是先来说一说今日景禹要给你们分享的内容,关键路径。何为关键路径?如果...
  • 简单理解关键路径

    千次阅读 多人点赞 2020-03-03 20:40:09
    一,关键路径问题的相关概念 ...关键路径是指能影响项目整体时间的活动和事件的集合,是项目中最长的路径。 关键路径问题也即指从多个子项目中流程中找到影响项目整体运营时间的关键路径。 对以上问题进行建...
  • AOE网络-关键路径

    千次阅读 多人点赞 2018-10-15 18:25:32
    拓扑排序的另一个应用就是关键路径的问题,关键路径对应的是另一种网络:AOE网络。先回顾下拓扑排序中讲到的AOV网络,AOV网络即“Activity On Vertex”,即图上每一个顶点表示的是一个事件或者说一个活动,而顶点...
  • 关键路径算法

    千次阅读 2016-04-06 18:09:12
    关键路径的算法是建立在拓扑排序的基础之上的,这个算法中用到了拓扑排序,所以在这里先以拓扑排序开篇。 1. 什么是拓扑排序? 举个例子先:一个软件专业的学生学习一系列的课程,其中一些课程必须再学完它的基础...
  • 关键路径核心算法

    千次阅读 2018-08-12 12:53:34
    关键路径核心算法:求一条不影响整体工程进度的最优路径方案,下面我将分为三个步骤详细讲解该算法。 第一步:求各个事件(结点)的最早时间(在这里我们用一个数组va[]来存储各个事件的最早时间)和最晚时间(在...
  • CPM关键路径

    2021-04-22 17:09:05
    目录CPM关键路径法定义构造方法CPM中节点表示例题关键路径的意义: CPM关键路径法 定义 关键路径法(CriticalPath Method, CPM)是一种基于数学计算的项目计划管理方法,是网络图计划方法的一种。关键路径法将项目...
  • 关键路径详细原理

    千次阅读 2018-07-18 20:30:21
     关键路径,顾名思义,就是一个程序中最关键的路径,它关系到整个程序的时间进度,而关键二字指临界点。 我们需要引进两个概念,AOE和AOV网。 二、AOE和AOV网  AOE和AOV网都是一个大型程序的示意图。而AOV关注...
  • 关键路径详解

    千次阅读 2019-11-22 15:46:36
    ),而把关键路径上的活动称为关键活动,显然关键活动会影响整个工程的进度。 关键概念: 1. 事件的最早发生时间 ve[k] ( earliest time of vertex ):即 顶点 vk 的最早发生时间。 从源点向终点方向...
  • AOE求关键路径

    千次阅读 2019-12-03 18:26:20
    在AOE图,一个事件发生的要求是通向其的活动全部结束,那么这么时间发生的最早时间就是与之相连的所有活动全部结束后的时间,而关键路径就是,使得事件都发生的路径。这个路径的时间一定是最长的。 基本思想 1.可以...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 103,949
精华内容 41,579
热门标签
关键字:

关键路径是事件