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

    2021-01-16 13:15:27
    //算法6.13 关键路径算法 #include <iostream> using namespace std; #define MVNum 100 //最大顶点数 #define BDNum MVNum * (MVNum - 1) //最大边数 #define OK 1 #define ERROR 0 typedef char ...
    //算法6.13 关键路径算法
    
    #include <iostream>
    using namespace std;
    
    #define MVNum 100                       	//最大顶点数
    #define BDNum MVNum * (MVNum - 1)			//最大边数
    #define OK 1	
    #define ERROR 0 
    
    typedef char VerTexType;
    
    //- - - - -图的邻接表存储表示- - - - - 
    typedef struct ArcNode{                		//边结点 
        int adjvex;                          	//该边所指向的顶点的位置
    	int weight;								//权值
        struct ArcNode *nextarc;          		//指向下一条边的指针 
    }ArcNode; 
    
    typedef struct VNode{ 
        VerTexType data;                    	//顶点信息
        ArcNode *firstarc;                		//指向第一条依附该顶点的边的指针 
    }VNode, AdjList[MVNum];               		//AdjList表示邻接表类型 
    
    typedef struct{ 
        AdjList vertices;                 		//邻接表 
    	AdjList converse_vertices;				//逆邻接表
        int vexnum, arcnum;              		//图的当前顶点数和边数 
    }ALGraph;
    //- - - - - - - - - - - - - - - -
    
    //- - - - -顺序栈的定义- - - - -
    typedef struct{
    	int *base;
    	int *top;
    	int stacksize;
    }spStack;
    //- - - - - - - - - - - - - - - -
    
    int indegree[MVNum];						//数组indegree存放个顶点的入度
    int ve[BDNum];								//事件vi的最早发生时间
    int vl[BDNum];								//事件vi的最迟发生时间
    int topo[MVNum];							//记录拓扑序列的顶点序号
    spStack S;
    
    //----------------栈的操作--------------------
    void InitStack(spStack &S){
    	//栈的初始化
    	S.base = new int[MVNum];
    	if(!S.base)
    		exit(1);
    	S.top = S.base;
    	S.stacksize = MVNum;
    }//InitStack
    
    void Push(spStack &S , int i){
    	//入栈
    	if(S.top - S.base == S.stacksize)
    		return;
    	*S.top++ = i;
    }//Push
    
    void Pop(spStack &S , int &i){
    	//出栈
    	if(S.top == S.base)
    		return;
    	i = *--S.top;
    }//Pop
    
    bool StackEmpty(spStack S){
    	//判断栈是否为空
    	if(S.top == S.base)
    		return true;
    	return false;
    }//StackEmpty
    //---------------------------------------
    
    int LocateVex(ALGraph G , VerTexType v){
    	//确定点v在G中的位置
    	for(int i = 0; i < G.vexnum; ++i)
    		if(G.vertices[i].data == v)
    			return i;
    		return -1;
    }//LocateVex
    
    int CreateUDG(ALGraph &G){ 
    	//创建有向图G的邻接表、逆邻接表
    	int i , k;
    	
    	cout <<"请输入总顶点数,总边数,以空格隔开:";
    	cin >> G.vexnum >> G.arcnum;				//输入总顶点数,总边数 
        cout << endl;
    
    	cout << "输入点的名称,如a" << endl;
    	
    	for(i = 0; i < G.vexnum; ++i){          		//输入各点,构造表头结点表
    		cout << "请输入第" << (i+1) << "个点的名称:";
    		cin >> G.vertices[i].data;           		//输入顶点值
    		G.converse_vertices[i].data = G.vertices[i].data;
    		//初始化表头结点的指针域为NULL 
    		G.vertices[i].firstarc=NULL;			
    		G.converse_vertices[i].firstarc=NULL;
        }//for
    	cout << endl;
    
    	cout << "输入边依附的顶点及其权值,如a b 3" << endl;
    
    	for(k = 0; k < G.arcnum;++k){        			//输入各边,构造邻接表
    		VerTexType v1 , v2;
    		int i , j , w;
    		cout << "请输入第" << (k + 1) << "条边依附的顶点及其权值:";
    		cin >> v1 >> v2 >> w;                		//输入一条边依附的两个顶点
    		i = LocateVex(G, v1);  j = LocateVex(G, v2);
    		//确定v1和v2在G中位置,即顶点在G.vertices中的序号 
    
    		ArcNode *p1=new ArcNode;               		//生成一个新的边结点*p1 
    		p1->adjvex=j;                   			//邻接点序号为j
    		p1->nextarc = G.vertices[i].firstarc;  G.vertices[i].firstarc=p1;
    		p1->weight = w;
    		//将新结点*p1插入顶点vi的边表头部
    
    		ArcNode *p2=new ArcNode;               		//生成一个新的边结点*p1 
    		p2->adjvex=i;                   			//逆邻接点序号为i
    		p2->nextarc = G.converse_vertices[j].firstarc;  G.converse_vertices[j].firstarc=p2;
    		p2->weight = w;
    		//将新结点*p1插入顶点vi的边表头部
        }//for 
        return OK; 
    }//CreateUDG
    
    void FindInDegree(ALGraph G){
    	//求出各顶点的入度存入数组indegree中 
    	int i , count;
    
    	for(i = 0 ; i < G.vexnum ; i++){
    		count = 0;
    		ArcNode *p = G.converse_vertices[i].firstarc;
    		if(p){
    			while(p){
    				p = p->nextarc;
    				count++;
    			}
    		}//if
    		indegree[i] = count;
    	}//for
    }//FindInDegree
    
    int TopologicalOrder(ALGraph G , int topo[]){ 
        //有向图G采用邻接表存储结构 
        //若G无回路,则生成G的一个拓扑序列topo[]并返回OK,否则ERROR 
    	int i , m;
        FindInDegree(G);              				//求出各顶点的入度存入数组indegree中 
        InitStack(S);                          		//栈S初始化为空 
        for(i = 0; i < G.vexnum; ++i)
    		if(!indegree[i]) Push(S, i);     		//入度为0者进栈 
    	m = 0;                               		//对输出顶点计数,初始为0 
    	while(!StackEmpty(S)){                		//栈S非空 
    		Pop(S, i);                          	//将栈顶顶点vi出栈
    		topo[m]=i;                         		//将vi保存在拓扑序列数组topo中 
    		++m;                             		//对输出顶点计数 
    		ArcNode *p = G.vertices[i].firstarc;    //p指向vi的第一个邻接点 
    		while(p){
    			int k = p->adjvex;					//vk为vi的邻接点   
    			--indegree[k];                   	//vi的每个邻接点的入度减1 
    			if(indegree[k] ==0)  Push(S, k);	//若入度减为0,则入栈 
    			p = p->nextarc;                		//p指向顶点vi下一个邻接结点 
    		}//while 
    	}//while
    	
    	if(m < G.vexnum)  return ERROR;    			//该有向图有回路 
    	else return OK;
    }//TopologicalOrder
    
    int CriticalPath(ALGraph G){ 
        //G为邻接表存储的有向网,输出G的各项关键活动
    	int n , i , k , j , e , l;
        if (!TopologicalOrder(G, topo))  return ERROR; 
        //调用拓扑排序算法,使拓扑序列保存在topo中,若调用失败,则存在有向环,返回ERROR 
        n = G.vexnum;                  				//n为顶点个数 
        for(i = 0; i < n; i++)               		//给每个事件的最早发生时间置初值0 
    		ve[i] = 0; 
    
    
        /*――――――――――按拓扑次序求每个事件的最早发生时间-――――-―――――*/ 
        for(i = 0;i < n; i++){                 
    		k = topo[i];                   			//取得拓扑序列中的顶点序号k             
    		ArcNode *p = G.vertices[k].firstarc;    //p指向k的第一个邻接顶点  
    		while(p != NULL){            			//依次更新k的所有邻接顶点的最早发生时间   
    			j = p->adjvex;               		//j为邻接顶点的序号                   
    			if(ve[j] < ve[k] + p->weight)    	//更新顶点j的最早发生时间ve[j] 
    				ve[j] = ve[k] + p->weight;     
    			p = p->nextarc;              		//p指向k的下一个邻接顶点  
    		} //while 
        } //for 
    
        for(i=0;i<n;i++)                 			//给每个事件的最迟发生时间置初值ve[n-1] 
    		vl[i]=ve[n-1];
    	
        /*――――――――――按逆拓扑次序求每个事件的最迟发生时间-――――-―――――*/ 
        for(i = n - 1;i >= 0; i--){               
    		k = topo[i];                   			//取得拓扑序列中的顶点序号k             
    		ArcNode *p = G.vertices[k].firstarc;    //p指向k的第一个邻接顶点  
    		while(p != NULL){            			//根据k的邻接点,更新k的最迟发生时间   
    			j = p->adjvex;              		//j为邻接顶点的序号                   
    			if(vl[k] > vl[j] - p->weight)    	//更新顶点k的最迟发生时间vl[k] 
    				vl[k] = vl[j] - p->weight;       
    			p = p->nextarc;              		//p指向k的下一个邻接顶点  
    		}//while 
        }//for 
    
        /*――――――――――――判断每一活动是否为关键活动-――――――-―――――*/
    	cout << endl;
    	cout << "关键活动路径为:";
        for(i = 0;i < n; i++){                		//每次循环针对vi为活动开始点的所有活动 
            ArcNode *p = G.vertices[i].firstarc;    //p指向i的第一个邻接顶点  
            while(p != NULL) {    
    			j = p->adjvex;             			//j为i的邻接顶点的序号    
    			e = ve[i];                 			//计算活动<vi, vj>的最早开始时间 
    			l = vl[j] - p->weight;      		//计算活动<vi, vj>的最迟开始时间 
    			if(e == l)               			//若为关键活动,则输出<vi, vj> 
    				cout << G.vertices[i].data << "-->" << G.vertices[j].data << " ";
    			p = p->nextarc;              		//p指向i的下一个邻接顶点  
    		} //while 
    	} //for  
    	return OK;
    }//CriticalPath
    
    int main(){
    	cout << "************算法6.13 关键路径算法**************" << endl << endl;
    	ALGraph G;
    	CreateUDG(G);
    	int *topo = new int [G.vexnum];
    	
    	cout << endl;
    	cout << "有向图创建完成!" << endl << endl;
    	
    	if(!CriticalPath(G))
    		cout << "网中存在环,无法进行拓扑排序!" <<endl << endl;
    	cout << endl;
    	return OK;
    }//main
    
    
    
    展开全文
  • 关键路径算法-完整版.pptx
  • 关键路径算法实现

    2019-09-27 01:16:40
    关键路径算法实现 代码 1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<iomanip.h> 4 #include <process.h> ...
    ContractedBlock.gifExpandedBlockStart.gif代码
    1 #include<stdio.h>
    2 #include<stdlib.h>
    3 #include<iomanip.h>
    4 #include <process.h>
    5
    6  //#define PROJECTNUMBER 9//10
    7
    8 //#define PLANNUMBER 11//13
    9 int SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);
    10 void CreateGraphic(Graphicmap,projectnumber,activenumber);
    11 typedef struct node
    12 {
    13 int adjvex;
    14 int dut;
    15 struct node *next;
    16 }edgenode;
    17
    18 typedef struct
    19 {
    20 int projectname;
    21 int id;
    22 edgenode *link;
    23 }vexnode;
    24
    25 //vexnode Graphicmap[PROJECTNUMBER];
    26
    27 void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber)
    28 {
    29 int begin,end,duttem;
    30 int i,k;
    31 edgenode *p;
    32 for(i=0;i<projectnumber;i++)
    33 {
    34 Graphicmap[i].projectname=i;
    35 Graphicmap[i].id =0;
    36 Graphicmap[i].link =NULL;
    37 }
    38 printf("某项目的开始到结束在图中的节点输入<vi,vj,dut>\n");
    39 printf("如:3,4,9 回车表示第三节点到第四节点之间的活动用了9个单位时间\n");
    40 for(k=0;k<activenumber;k++)
    41 {
    42 scanf("%d,%d,%d",&begin,&end,&duttem);
    43 p=(edgenode*)malloc(sizeof(edgenode));
    44 p->adjvex =end-1;
    45 p->dut =duttem;
    46 Graphicmap[end-1].id ++;
    47 p->next =Graphicmap[begin-1].link ;
    48 Graphicmap[begin-1].link =p;
    49 }
    50 }
    51
    52 int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int totaltime)
    53 {
    54 int i,j,k,m=0;
    55 int front=-1,rear=-1;
    56 int* topologystack=(int*)malloc(projectnumber*sizeof(int));//用来保存拓扑排列
    57 int* vl=(int*)malloc(projectnumber*sizeof(int));//用来表示在不推迟整个工程的前提下,VJ允许最迟发生的时间
    58 int* ve=(int*)malloc(projectnumber*sizeof(int));//用来表示Vj最早发生时间
    59 int* l=(int*)malloc(activenumber*sizeof(int));//用来表示活动Ai最迟完成开始时间
    60 int* e=(int*)malloc(activenumber*sizeof(int));//表示活动最早开始时间
    61 edgenode *p;
    62 totaltime=0;
    63 for(i=0;i<projectnumber;i++) ve[i]=0;
    64 for(i=0;i<projectnumber;i++)
    65 {
    66 if(Graphicmap[i].id==0)
    67 {
    68 topologystack[++rear]=i;
    69 m++;
    70 }
    71 }
    72 while(front!=rear)
    73 {
    74 front++;
    75 j=topologystack[front];
    76 m++;
    77 p=Graphicmap[j].link ;
    78 while(p)
    79 {
    80 k=p->adjvex ;
    81 Graphicmap[k].id --;
    82 if(ve[j]+p->dut >ve[k])
    83 ve[k]=ve[j]+p->dut ;
    84 if(Graphicmap[k].id ==0)
    85 topologystack[++rear]=k;
    86 p=p->next ;
    87 }
    88 }
    89 if(m<projectnumber)
    90 {
    91 printf("\n本程序所建立的图有回路不可计算出关键路径\n");
    92 printf("将退出本程序\n");
    93 return 0;
    94 }
    95 totaltime=ve[projectnumber-1];
    96 for(i=0;i<projectnumber;i++)
    97 vl[i]=totaltime;
    98 for(i=projectnumber-2;i>=0;i--)
    99 {
    100 j=topologystack[i];
    101 p=Graphicmap[j].link ;
    102 while(p)
    103 {
    104 k=p->adjvex ;
    105 if((vl[k]-p->dut )<vl[j])
    106 vl[j]=vl[k]-p->dut ;
    107 p=p->next ;
    108 }
    109 }
    110 i=0;
    111 printf("| 起点 | 终点 | 最早开始时间 | 最迟完成时间 | 差值 | 备注 |\n");
    112 for(j=0;j<projectnumber;j++)
    113 {
    114 p=Graphicmap[j].link;
    115 while(p)
    116 {
    117 k=p->adjvex ;
    118 e[++i]=ve[j];
    119 l[i]=vl[k]-p->dut;
    120 printf("| %4d | %4d | %4d | %4d | %4d |",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,e[i],l[i],l[i]-e[i]);
    121 if(l[i]==e[i])
    122 printf(" 关键活动 |");
    123 printf("\n");
    124 p=p->next ;
    125 }
    126 }
    127 return 1;
    128 }
    129
    130 void seekkeyroot()
    131 {
    132 int projectnumber,activenumber,totaltime=0;
    133 vexnode* Graphicmap;
    134 system("cls");
    135 printf("请输入这个工程的化成图形的节点数:");
    136 scanf("%d",&projectnumber);
    137 printf("请输入这个工程的活动个数:");
    138 scanf("%d",&activenumber);
    139 Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode));
    140 CreateGraphic(Graphicmap,projectnumber,activenumber);
    141 SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);
    142 printf("整个工程所用的最短时间为:%d个单位时间\n",totaltime);
    143 system("pause");
    144 }
    145
    146 int main()
    147 {
    148 char ch;
    149 int i;
    150 for(;;)
    151 {
    152 do
    153 {
    154 system("cls");
    155 printf("| 欢迎进入求关键路径算法程序 |");
    156 for(i=0;i<80;i++)printf("*");
    157 printf("%s","(S)tart开始输入工程的节点数据并求出关键路径\n");
    158 printf("%s","(E)xit退出\n");
    159 printf("%s","请输入选择:");
    160 scanf("%c",&ch);
    161 ch=toupper(ch);
    162 }while(ch!='S'&&ch!='E');
    163 switch(ch)
    164 {
    165 case'S':
    166 seekkeyroot();
    167 break;
    168 case'E':
    169 return 1;
    170 }
    171 }
    172 }
    173
    174

     

    posted on 2010-06-25 14:42 rockysy 阅读(...) 评论(...) 编辑 收藏

    转载于:https://www.cnblogs.com/whg841001/archive/2010/06/25/1765167.html

    展开全文
  • # 关键路径算法def critical_path(orthogonal_graph): # 初始化最早结点开始时间 etv = [0 for i in range(len(orthogonal_graph.vertex_list))] # 初始化拓扑序列栈 stack = queue.LifoQueue() # 进行拓扑排序,将...

    我原来是学工业工程出身,第一份工作出来做的是生产线优化。在一条流水线上,总是会出现一个工作之前要有很多个前置工作,而前置工作往往是可以并行的。

    就比如你要组装一辆汽车,那么组装这个操作之前就有很多个并行的前置工作,比如加工轮胎,加工地盘,加工发动机等等。这些单独的前置工作又会有各自的前置,这就形成了一个前后制约的流水线。

    在流水线中,往往会有一条加工线,他花费的时间最长,制约着整个流水线最终的效率。那这样的一条加工线,就是关键线路,我当时在生产线上的工作就是找到这个关键线路,然后优化其中制约效率的结点,从而让整体的生产效率提升。

    当年因为负责的生产型并非十分的复杂,所以这种工作用图表也就可以勉强的解决了。那如果是加工一辆汽车,有成千上万个零件和对应的工序,那么想在这中间找到那条制约整个加工效率的关键路径就并不是非常的容易了。这时候就需要借助计算机的帮助。

    811a8f7de0ef912bb59a4cab03bd013c.png

    用计算机的思路对这个问题进行抽象,就可以把加工的流水线看做是一个有向无环的网,其中每一条弧代表一个加工作业,而每一个弧上的权重代表着这个作业花费的时间,而弧和结点的相互顺序,代表了作业的前置依赖。我想要找到的也就是这个网中,从起始点到终点的关键路径。

    图中A,B是两个起始节点,他们的入度为0,而I为最终节点,他的出度为0。那我们的目的,就是要找到从A,B到I的路径,这条路径上的加工作业时间决定了整体加工作业的用时。

    关键路径有什么特征?

    我们知道一个工作有最早的开始时间也有最晚的开始时间。就比如你老板给了你个工作,要求是今天下班前给他。这个工作之前你需要小张把材料给你,但他说要下午两点才能给你。你评估了一下这个工作只要2个小时就可以完成了。而下午两点到下班中间有四个小时。

    那么你这个工作最早的开始时间就是下午2点,再早了你都没有材料,那最晚的开始时间是下午四点,因为再晚你6点下班前给不出东西来了。所以你这个工作就有两个时间最早开始和最晚开始时间,但是他们并不一样(一个2点,一个4点)。

    那你出去了解了一下,老板之所以是下班才要这个东西,是因为他同时还让小赵做了另一个材料,你们俩的工作合在一起才有用。而小赵这个东西很麻烦要4个小时,他也是最早下午2点才能从小王那边拿到材料。所以小赵的工作最早开始时间是2点,最晚开始时间也是2点。

    那想让老板更早拿到成品,提升你的效率还是提升小赵的呢?当然是小赵的,因为你做的再快也不会减少这个流程的时间了。这时候小赵的工作就是关键路径。他有什么特征呢?

    关键路径的特征,最早开始时间和最晚开始时间是一样的,他没有调整的空间。

    怎么求出最早开始时间和最晚开始时间?

    想要求出边的最早开始时间和最晚开始时间,我们需要借助结点的最早开始时间和最晚开始时间。假设对于一条弧,那么他最早的开始时间,就是结点D的最早开始时间。而最晚开始时间,就是G的最晚开始时间减去弧的权重。所以只要知道了结点最早,最晚开始时间,就可以算出来弧的时间。

    那么如何求出结点的最早开始时间和最晚开始时间呢?

    我们可以利用拓扑排序的方式,来计算出结点前置路径最大的那一个,就是这个节点的最早开始时间了。这个的含义是这个结点前面的工作中最慢的一个要用这么久,所以这个结点最早开始时间。

    而获得最晚开始时间,则把拓扑排序的过程反过来。先得到最后一个结点的完成时间,倒推回去,取后置结点的最晚时间减去权重的最小值。这个含义是deadline已经确定了,工作时间也确定了,你至少要比这个时间早开始才能做得完。

    举个例子,就拿G结点来说。他的最早开始时间是比较一下到达他的前面几条路径,分别是=6,=8,=8,=6。因为其中最长耗时的路径为8,所以G点不能比8点开始更早了。

    同样的求G的最晚开始时间,假设已经知道I的最晚开始时间为13。因为=3,所以G的最晚开始时间就是13-3=10。

    这样我们就有了结点的最早,最晚开始时间,也就可以算出边的最早最晚开始时间,进而得到关键路径了。

    代码实现

    因为需要知道结点的前后边,所以图的存储结构采用十字链表(图的存储方式(二)),关键路径的实现如下。

    # 关键路径算法def critical_path(orthogonal_graph):    # 初始化最早结点开始时间    etv = [0 for i in range(len(orthogonal_graph.vertex_list))]    # 初始化拓扑序列栈    stack = queue.LifoQueue()    # 进行拓扑排序,将拓扑排序节点压如栈中,更新最早结点开始时间    # 建立入度为0的节点队列    q_ready = queue.Queue()    # 拓扑序列    topo_list = []    # 计算图中每一个节点的入度    for v_index in range(len(orthogonal_graph.vertex_list)):        v = orthogonal_graph.vertex_list[v_index]        # 初始入度为0        v.in_degree = 0        if v.first_in is None:            # 入度为0放入到准备队列            q_ready.put(v_index)        else:            e = v.first_in            # 遍历边集列表,计算入度            while e is not None:                v.in_degree += 1                e = e.head_link    # 如果入度为空队列里面有节点,就处理,没有待处理的节点,就结束输出拓扑序列    while not q_ready.empty():        v_index = q_ready.get()        # 该处与拓扑序列操作不同,将结点压如栈中        stack.put(v_index)        topo_list.append(v_index)        # 更新相邻指向节点的入度        e = orthogonal_graph.vertex_list[v_index].first_out        while e is not None:            v_next = orthogonal_graph.vertex_list[e.head_vex]            v_next.in_degree -= 1            # 如果更新之后的节点入度为零,加入到待处理列表中            if v_next.in_degree == 0:                q_ready.put(e.head_vex)            # 更新结点最小开始时间            etv[e.head_vex] = max(etv[e.head_vex],etv[e.tail_vex]+e.weight)            # 指向下一条边            e = e.tail_link    # 初始化最晚结点开始时间,所有的节点时间设置为最后一个结点的开始时间。    ltv = [etv[-1] for i in range(len(orthogonal_graph.vertex_list))]    # 反向操作拓扑序列,计算每一个结点的最晚开始时间    while not stack.empty():        # 从栈中取出拓扑序列最后面的结点        v_index = stack.get()        v = orthogonal_graph.vertex_list[v_index]        # 遍历指向该节点的弧,更新结点的最晚开始时间。        e = v.first_in        while e is not None:            # 更新最晚开始时间            ltv[e.tail_vex] = min(ltv[e.tail_vex],ltv[e.head_vex]-e.weight)            # 更新下一条指向该结点的弧            e = e.head_link    print('etv',etv)    print('ltv',ltv)    # 求关键路径,弧的最早开始时间和最晚开始时间一样的时候,则为关键路径。    # 求弧的最早开始时间和最晚开始时间。    for v_index in range(len(orthogonal_graph.vertex_list)):        # 结点        v = orthogonal_graph.vertex_list[v_index]        # 结点的出弧        e = v.first_out        # 遍历弧        while e is not None:            # 弧的最早开始时间            ete = etv[e.tail_vex]            # 弧的最晚开始时间            lte = ltv[e.head_vex] - e.weight            if ete == lte:                print(' ' % (orthogonal_graph.vertex_list[e.tail_vex].data,orthogonal_graph.vertex_list[e.head_vex].data),end='')            # 指向下一个弧            e = e.tail_link

    实验一下上面那张图,看看关键路径是什么

    vertex_list = ['A','B','C','D','E','F','G','H','I']graph_matrix = [[0,INFINITY,1,2,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY],                [INFINITY,0,INFINITY,2,3,INFINITY,INFINITY,INFINITY,INFINITY],                [INFINITY,INFINITY,0,INFINITY,INFINITY,4,5,INFINITY,INFINITY],                [INFINITY,INFINITY,INFINITY,0,INFINITY,INFINITY,6,INFINITY,INFINITY],                [INFINITY,INFINITY,INFINITY,INFINITY,0,INFINITY,3,7,INFINITY],                [INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,0,INFINITY,INFINITY,5],                [INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,0,3,4],                [INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,0,2],                [INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,0]]orth_graph = OrthogonalGraph()orth_graph.build(vertex_list,graph_matrix)critical_path(orth_graph)

    结果显示的关键路径如下:

    etv [0, 0, 1, 2, 3, 5, 8, 11, 13]ltv [0, 0, 3, 2, 4, 8, 8, 11, 13]  

    END

    2fc92a6fbe1719519a700fb40d7f191a.png

    作者:锅哥不姓郭

       图片:网络(侵删)

    300ad661a9730b672adf4ee73bc3e380.png

    展开全文
  • 拓扑排序关键路径算法C语言完整代码,vs2013下编译运行通过
  • Prim算法、Kruskal算法、Dijkstra算法、Floyd算法、拓扑排序算法、关键路径算法

    构造一个邻接矩阵图

    #include<iostream>
    #include<string>
    #include<bits/stdc++.h>
    using namespace std;
    const int Maxsize=100;
    const int Max=999;
    template<class T>
    class Graph
    {
    private:
        T dian[Maxsize];
        int fl[Maxsize];
        int bian[Maxsize][Maxsize];
        int di,bi;
    public:
        Graph(T a[],int n,int e);
        void DFSTraverse(int v);
        void print();
        void Dijstra(int st,int et);
        void floyd();
        void prim();
    };
    template<class T>
    Graph<T>::Graph(T a[],int n,int e){
        di=n;
        bi=e;
        for(int i=0;i<di;i++)
        {
            fl[i]=0;
            dian[i]=a[i];
        }
        for(int i=0;i<di;i++)
        {
            for(int j=0;j<di;j++)
             {
                 cin>>bian[i][j];
             }
        }
    
    }
    

    最小生成树

    生成树的代价:设G=(V,E)是一个无向连通网,生成树上各边的权值之和称为该生成树的代价。
    最小生成树:在图G所有生成树中,代价最小的生成树称为最小生成树。
    最小生成树的概念可以应用到许多实际问题中。
    例:在n个城市之间建造通信网络,至少要架设n-1条通信线路。
    而每两个城市之间架设通信线路的造价是不一样的,那么如何设计才能使得总造价最小?

    Prim算法

    基本思想:
    设G=(V, E)是具有n个顶点的连通网,
    T=(U, TE)是G的最小生成树,
    T的初始状态为U={u0}(u0∈V),TE={ },
    重复执行下述操作:
    在所有u∈U,v∈V-U的边中找一条代价最小的边(u, v)并入集合TE,同时v并入U(加点法),直至U=V。

    template<class T>
    void Graph<T>::prim()
    {
        int lowcost[Maxsize];//从S点集到U-s点集中每个点的边(注意不是S中每个点到U-S中每个点)
        int s[Maxsize];//S点集合记录最小生成树,生成过程中加入节点过程
            for(int i=0;i<di;i++)
            lowcost[i]=bian[0][i];//初始化数组,第一个点为源点
         s[0]=0;//初始化S点集合,源点为第一个元素
        int num=1;
        lowcost[0]=0;//所有U-S中元素加入到S后,都作上标记
        while(num<di)//num表示S点集中点的数量,当所有S点击中元素数量等于总点数量表示,最少生成树已生成。
        {
            int k=0;
            lowcost[k]=100;//用第一个边,开始寻找最小边
            for(int i=1;i<di;i++)
            {
                if(lowcost[i]<lowcost[k]&&lowcost[i]!=0) k=i;
            }
            cout<<lowcost[k]<<" ";//找到最小边
            lowcost[k]=0;//此边已用作上标记,这样不用真的从内存中删除它
            for(int j=1;j<di;j++)
            {//用将刚刚找到的最小边的U-S的一端的点,去更新Lowcost
                if(bian[k][j]<lowcost[j])//更新从S点集到U-s点集中每个点的边
                {//被标记为0的不用担心会被改变
                    lowcost[j]=bian[k][j];
                    s[j]=k;//这里其实只用写num++位置上,但是没关系,多写入的会被下一次循环覆盖
                }
            }
             num++;//更新完lowcost后、也加入k后,就可以放心更新S集合元素数量了
        }
    }
    

    Kruskal算法

    基本思想:
    设无向连通网为G=(V, E),令G的最小生成树为T=(U, TE),其初态为U=V,TE={ },
    然后,按照边的权值由小到大的顺序,考察G的边集E中的各条边。(加边法)
    若被考察的边的两个顶点属于T的两个不同的连通分量,则将此边作为最小生成树的边加入到T中,同时把两个连通分量连接为一个连通分量;
    若被考察边的两个顶点属于同一个连通分量,则舍去此边,以免造成回路,
    如此下去,当T中的连通分量个数为1时,此连通分量便为G的一棵最小生成树。
    图的存储结构
    采用边集数组存储图。
    如何判断一条边所依附的两个顶点在同一个连通分两中(并查集)
    定义Parent[i]数组。数组分量的值表示顶点i的双亲节点(初值为-1;)
    当一条边(u,v)的两个顶点的根结不同时,这两个结点属于不同的连通分量(利用parent 数组查找一棵树的根节点。当一个结点n的parent==-1,树的根节点即为n)
    如何将一条边所依附的两个顶点合并到同一个连通分量中
    要进行联通分量的合并 ,其中一个顶点所在的树的根节点为vex1,另一个顶点所在的树的根节点为vex2,则:parent[vex2]=vex1;

    #include<bits/stdc++.h>
    using namespace std;
    struct edge//边集数组
    {
        int from;
        int to;
        int weight;//代价
    };
        bool compare(edge a,edge b)
        {
            return a.weight<b.weight;
        }
        int find(int a[],int node)//并查集查找
        {int f;
        f=node;
        while(a[f]>-1){
            f=a[f];
        }
            return f;
        }
    int main()
    {
        int di,bi;
        edge ed[100];
        int dian[100];
        int parent[100];
        cin>>di>>bi;
        int g=-1;
        for(int i=0;i<di;i++)//初始化边集
        {
            for(int j=0;j<di;j++)
            {int t;
                cin>>t;
                if(t!=0&&t!=100&&i<j)
                {
                     g++;
                     ed[g].from=i;
                     ed[g].to=j;
                     ed[g].weight=t;
                }
            }
        }
        sort(ed,ed+bi,compare);//排序
        for(int i=0;i<bi;i++)
        {
            parent[i]=-1;//初始化并查集
           
        }
        int k=0,begin,end,count=0;
        for(int k=0;k<bi;k++)
        {
            begin=ed[k].from;
            end=ed[k].to;
            int m,n;
            m=find(parent,begin);
            n=find(parent,end);
           
            if(m!=n){//m,n不在同一个连通分量
                cout<<begin+1<<" "<<end+1<<" ";
                parent[n]=m;//修改并查集,这条边在后续无法使用
                count++;
                if(count==di-1) break;
            }
        }
        return 0;
    }
    

    性能分析
    边集数组排序,时间复杂性O(eloge)//此代码中没有使用堆排序,堆排序请参考我博客中的排序技术
    在e条边中选边,时间复杂性为O(e)
    因此时间复杂性为O(eloge)

    最短路径

    在网图中,最短路径是指两顶点之间经历的边上权值之和最短的路径。

    单源点最短路径问题

    问题描述:给定带权有向图G=(V, E)和源点v∈V,求从v到G中其余各顶点的最短路径。
    应用实例——计算机网络传输的问题:怎样找到一种最经济的方式,从一台计算机向网上所有其它计算机发送一条消息。
    **迪杰斯特拉(Dijkstra)**提出了一个按路径长度递增的次序产生最短路径的算法——Dijkstra算法。

    template<class T>
    void Graph<T>::Dijstra(int st,int et)
    {
        string path[Maxsize];//路径数组,记录单源点到各个点的路径
        int dist[Maxsize];//路径长度数组,记录单源点到各个点的路径长度
        int s[Maxsize];//点数组,记录已经加入的点
        stringstream ss;
        ss<<dian[st];
        string stt=ss.str();//将整形转化为字符串的一种方法
        for(int i=0;i<di;i++)//初始化
        {
            dist[i]=bian[st][i];
            if(dist[i]!=Max)//源点和该点有边直接相连
            {
                stringstream sss;
        sss<<dian[i];
        string sttt=sss.str();
        path[i]="v"+stt+" "+"v"+sttt;
            }
            else{
                path[i]="";
            }
        }
        s[0]=dian[st];//先将源点自己加入
       int  num=1;//记录已经加入点数
        while(num<di)
        {
            int k=0;
            for(int i=0;i<di;i++)
            {
                if(dist[i]<dist[k]&&fl[i]==0)  k=i;//挑选出源点到各点路径中路径长度最小的点,fi数组是标记该点是否被选出过。
            }
            fl[k]=1;//修改标记
            s[num++]=dian[k];//将挑选出来的点,放到点集中,num++计数
            for(int i=0;i<di;i++)
            {
               if(dist[k]+bian[k][i]<dist[i])//判断源点经这个点到其他点长度是否比直接到达更短,如果更短则修改路径长度和路径
               {
                   dist[i]=dist[k]+bian[k][i];//修改路径长度
                   stringstream ssss;
        ssss<<dian[i];
        string stttt=ssss.str();
                   path[i]=path[k]+" "+"v"+stttt;//修改路径
               }
            }
    
        }
        if(dist[et]!=Max){
    
        cout<<dist[et]<<endl;
        cout<<path[et]<<endl;}
        else
            cout<<"no answer"<<endl;
    }
    

    每一对顶点之间的最短路径

    问题描述:给定带权有向图G=(V, E),对任意顶点vi,vj∈V(i≠j),求顶点vi到顶点vj的最短路径。

    解决办法1:每次以一个顶点为源点,调用Dijkstra算法n次。显然,时间复杂度为O(n3)。(注意对此调用则保证Dijkstra算法中的标记数组一定要每次更新,保证每次调用都是用原始状态去求下一个单元点最短路径
    解决办法2:弗洛伊德提出的求每一对顶点之间的最短路径算法——Floyd算法,其时间复杂度也是O(n3),但形式上要简单些。

    template<class T>
    void Graph<T>::floyd()
    {
        string path[Maxsize][Maxsize];//路径数组,记录各个点之间的路径
        int dist[Maxsize][Maxsize];//路径长度数组,记录各个点之间的路径长度
    
        for(int i=0;i<di;i++)初始化path和dist
        {
            stringstream ss;
        ss<<dian[i];
        string stt=ss.str();
            for(int j=0;j<di;j++)
            {
                dist[i][j]=bian[i][j];
                if(dist[i][j]!=Max) {
                        stringstream sss;
        sss<<dian[j];
        string sttt=sss.str();
                    path[i][j]="v"+stt+" "+"v"+sttt;
                }
            }
        }
        int num=0;//从下标为0的点,依次将各个点加入路径比较
        while(num<di)
        {
            for(int i=0;i<di;i++)
            {
                for(int j=0;j<di;j++)
                {
                    if(dist[i][num]+dist[num][j]<dist[i][j])
                    {
                        dist[i][j]=dist[i][num]+dist[num][j];//修改路径长度
                                      stringstream ssss;
        ssss<<dian[j];
        string stttt=ssss.str();
                        path[i][j]=path[i][num]+" "+"v"+stttt;//修改路径
                    }
                }
            }
            num++;//下一个点
        }
        for(int i=0;i<di;i++)
        {
            for(int j=0;j<di;j++)
            {if(i!=j){
                if(dist[i][j]!=Max){
    
        cout<<dist[i][j]<<" "<<path[i][j]<<endl;}
        else
            cout<<"no answer"<<endl;
            }
            }
        }
    
    }
    

    拓扑排序

    AOV网:在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,称这样的有向图为顶点表示活动的网,简称AOV网。
    AOV网特点:
    1、AOV网中的弧表示活动之间存在的某种制约关系。
    2、AOV网种不能出现回路
    拓扑序列:
    设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列v1, v2, …, vn称为一个拓扑序列,当且仅当满足下列条件:若从顶点vi到vj有一条路径,则在顶点的拓扑序列中顶点vi必在顶点vj之前。
    拓扑排序:对一个有向图构造拓扑序列的过程称为拓扑排序 。拓扑序列使得AOV网中所有应存在的前驱和后继关系都能得到满足。
    在这里插入图片描述基本思想:
    ⑴ 从AOV网中选择一个没有前驱的顶点并且输出;
    ⑵ 从AOV网中删去该顶点,并且删去所有以该顶点为尾的弧;
    ⑶ 重复上述两步,直到全部顶点都被输出,或AOV网中不存在没有前驱的顶点。
    设计存储结构
    在这里插入图片描述代码实例

    #include<bits/stdc++.h>
    using namespace std;
    const int Max=100;
    struct bian{//结点
    int xiabiao;
    bian *next;
    };
    struct VertexNode{//表头
    int in;//入度
    int xh;//下标
    bian *firstedge;};//该结点相连的弧头
    class Graph{
    private:
        VertexNode adjlist[Max];
        int vertexNum,arcNum;
    public:
        Graph(int n,int e);
        //~Graph();
        void TopSort();
    };
    Graph::Graph(int n,int e)
    {
        vertexNum=n;
        arcNum=e;
         bian *s;
        for(int i=0;i<vertexNum;i++)
        {
            adjlist[i].in=0;
            adjlist[i].xh=i+1;
            adjlist[i].firstedge=NULL;
        }
        for(int k=0;k<arcNum;k++){
            int i,j;
            cin>>i>>j;
            adjlist[j-1].in+=1;
            s=new bian;
            s->xiabiao=j-1;
            s->next=adjlist[i-1].firstedge;
            adjlist[i-1].firstedge=s;
        }
    }
    void Graph::TopSort(){
      int   count=0;
      set<int> s;//保证永远都是较小结点先输出
      set<int>::iterator it;
      int j;
      for(int i=0;i<vertexNum;i++)
          if(adjlist[i].in==0) s.insert(i);//将入度为0的结点存入set容器
      while(!s.empty()){
    
        it=s.begin();//按顺序取出元素
        j=*it;
        s.erase(j);//删除刚刚取出的元素避免重复
         cout<<"v"<<adjlist[j].xh<<" ";//输出这个元素
          count++;//标记元素个数
        bian *p;
        int k;
        p=adjlist[j].firstedge;
        while(p!=NULL){//删去所有以该顶点为尾的弧,也就是修改这些弧头的入度
              k=p->xiabiao; adjlist[k].in--;
             if(adjlist[k].in==0) s.insert(k);//遇到入度为0的元素将其加入容器
             p=p->next;
          }
       }
       if (count<vertexNum) cout<<"有回路";
    }
    int main()
    {
        int n,e;
        cin>>n>>e;
        Graph aa(n,e);
        aa.TopSort();
    }
    
    
    

    关键路径

    AOE网:
    在一个表示工程的带权有向图中,
    用顶点表示事件
    用有向边表示活动
    边上的权值表示活动的持续时间
    称这样的有向图叫做边表示活动的网,简称AOE网。
    AOE网中没有入边的顶点称为始点(或源点),没有出边的顶点称为终点(或汇点)。

    AOE网的性质:
    ⑴ 只有在某顶点所代表的事件发生后,从该顶点出发的各活动才能开始;
    ⑵ 只有在进入某顶点的各活动都结束,该顶点所代表的事件才能发生。
    AOE网可以回答下列问题:
    1、完成整个工程至少需要多少时间?
    从始点到终点的路径可能不止一条,只有各条路径上所有活动都完成了,整个工程才算完成。
    因此,完成整个工程所需的最短时间取决于从始点到终点的最长路径长度,即这条路径上所有活动的持续时间之和。
    这条路径长度最长的路径就叫做关键路径。
    2、为缩短完成工程所需的时间, 应当加快哪些活动?
    关键路径:在AOE网中,从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径称为关键路径。
    关键活动:关键路径上的活动称为关键活动。

    思路
    要找出关键路径,必须找出关键活动, 即不按期完成就会影响整个工程完成的活动。
    前期工作:
    ⑴ 事件的最早发生时间ve[k]
    ve[k]是指从始点开始到顶点vk的最大路径长度。这个长度决定了所有从顶点vk发出的活动能够开工的最早时间。
    ⑵ 事件的最迟发生时间vl[k]
    vl[k]是指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。
    ⑶ 活动的最早开始时间e[i]
    若活动ai是由弧<vk , vj>表示,则活动ai的最早开始时间应等于事件vk的最早发生时间。因此,有: e[i]=ve[k]
    ⑷ 活动的最晚开始时间l[i]
    活动ai的最晚开始时间是指,在不推迟整个工期的前提下, ai必须开始的最晚时间。
    若ai由弧<vk,vj>表示,则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。

    最后计算各个活动的时间余量 l[k] - e[k],时间余量为0者即为关键活动。
    存储结构的选择:
    为处理方便,同时采用了邻接矩阵和边集数组两种存储结构。
    邻接矩阵可以方便的查找邻接点,完成时间的最早和最晚发生时间的计算。
    边集数组可以方便的计算时间的活动的最晚发生时间

    #include<bits/stdc++.h>
    using namespace std;
    struct vdian{//事件
    int ve;//事件最早发生时间
    int vl;};//事件最晚发生时间
    struct edian{//活动(边集数组)
    int e;//活动最早发生时间
    int l;//活动最晚发生时间
    int fr;//活动起点事件
    int to;};//活动终点事件
    const int Max=100;
    class Graph
    {
    private:
        int vertexnum,arcnum;
        int len[Max][Max];//邻接矩阵
        vdian vd[Max];
        edian ed[Max];
    public:
        Graph(int n,int e);
        void guanjian();
    };
    Graph::Graph(int n,int e)
    {
        vertexnum=n;//初始化点数
        arcnum=e;//初始化边数
        int i,j;
        for(i=0;i<vertexnum;i++)//初始化事件
        {
            vd[i].ve=0;
            vd[i].vl=0;
            for(j=0;j<vertexnum;j++)
            {
                len[i][j]=Max;//初始化邻接矩阵
            }
        }
        int t=0;
        while(t<arcnum){//初始化活动边集
            ed[t].e=0;
            ed[t].l=0;
            cin>>i>>j;
            ed[t].fr=i;
            ed[t].to=j;
            cin>>len[i-1][j-1];//修改邻接矩阵
            t++;
        }
    }
    void Graph::guanjian()
    {
        //cout<<"Y";
        int t=0;
        while(t<vertexnum)//求事件最早发生时间
        {
            for(int j=0;j<vertexnum;j++)
            {
                if(len[t][j]!=Max&&vd[t].ve+len[t][j]>vd[j].ve)
                {
                    vd[j].ve=vd[t].ve+len[t][j];
                }
            }
            t++;
        }
        t=0;
        while(t<vertexnum)//修改事件最晚发生事件
        {
            vd[t].vl=vd[vertexnum-1].ve;
            t++;
        }
       t=vertexnum-1;
        while(t>=0)//求事件最晚发生时间
        { 
            for(int j=0;j<vertexnum;j++)
            {
                if(len[j][t]!=Max&&vd[t].vl-len[j][t]<vd[j].vl)
                {
                    vd[j].vl=vd[t].vl-len[j][t];
                }
            }
            t--;
        }
        t=0;
        for(int i=0;i<vertexnum;i++)
            for(int j=0;j<vertexnum;j++)
        {
            if(len[i][j]!=Max) ed[t++].e=vd[i].ve;//求活动最早发生时间
        }
         t=0;
        for(int i=0;i<vertexnum;i++)
            for(int j=0;j<vertexnum;j++)
        {
            if(len[i][j]!=Max) ed[t++].l=vd[j].vl-len[i][j];//求活动最晚发生时间
        }
         t=0;
         while(t<arcnum)
         {
              if(ed[t].e==ed[t].l)//t为关键活动
              {   /* if(t==0)   cout<<"v"<<ed[t].fr<<" "<<"v"<<ed[t].to<<" ";
              if(t==arcnum-1)   cout<<"v"<<ed[t].fr<<" "<<"v"<<ed[t].to<<" ";
                else cout<<"v"<<ed[t].fr<<" "<<"v"<<ed[t].to<<" ";//按要求输出关键路径*
              }
              t++;
         }
    }
    int main()
    {
        int n,e;
        cin>>n>>e;
        Graph aa(n,e);
        aa.guanjian();
    }
    
    
    展开全文
  • 第5-2课讲了拓扑排序算法,对应了第一个问题的解决方案,这一课将介绍关键路径算法,就是为了解决第二个问题,最短完成时间常常由工程活动中的关键路径决定,只有这个路径上的一系列活动顺理开展,项目或者工程的...
  • 在学习了拓扑排序之后,我们可以开始学习关键路径了。拓扑排序可以有多个起点和多个终点,跟拓扑排序不同的是,关键路径只能有一个起点、一个终点。 我们使用带有权重的有向图表示,8 -> 0 -> 1 -> 4 ->...
  • 拓扑排序主要是为解决一个工程能否顺序进行的问题,但有时我们还需要解决工程完成需要的最短时间问题。... 关键路径算法基于拓扑排序算法,这里直接上代码,以后有机会再详解。  class EdgeNode  { ...
  • 针对项目管理中关键路径计算这个核心问题,分析了关键路径算法的传统解决方式,深入研究了面向对象方式下解决这个问题的方法,给出了完整、洁净的解决方案,对用面向对象方式解决其他经典问题有帮助。
  • [算法]详解关键路径算法

    千次阅读 2017-01-09 10:20:22
    详解关键路径算法#include #include using namespace std; int eventsSize, activitiesSize; int activitiesCostTimes[100][100]; pair, int> activities[100]; int eventEarlyBegin[100], eventLate
  • 采用邻接矩阵表示项目活动网络图需要较多的存储空间,且基于结构化程序设计思想实现网络图和关键路径算法都非常繁琐。采用面向对象的类表示活动,基于动态数组表示活动网络图及活动之间的逻辑关系,并据此开发了基于...
  • AOV网——类似于拓扑排序的样子,即用有向图来描述和分析一项工程和计划的实施过程。 AOE网——即在AOV网上加上权重,有向图中以顶点表示事件,有向边代表活动,边上的权重...关键路径算法:   关键路径:AOE...
  • 用c#写的关键路径算法 给出关键路径计算的类
  • 【算法】基于AOE网的关键路径算法

    千次阅读 2017-09-28 15:58:21
    在工程上,我们都很讨厌工程的延期,同时一个工程由分为很多的节点,我们不知道哪些节点决定着这个工程是否会延期,每一个部分有没有可以伸缩的时间,于是,这个用来计划工程的关键路径算法就诞生了。看来,数据结构...
  • 关键路径算法演示过程,指用顶点表示活动,用弧表示活动间的优先关系的有向图称为顶点表示活动的网。
  • 邻接矩阵、邻接表中任选一种作为图的存储结构,AOE网关键路径算法,实现从AOE网源点到汇点的关键路径(2学时) 三、算法思路分析 四、算法反思 五、代码实现 #include<stdio.h> #include<stdlib.h> #...
  • 数据结构中关键路径算法的实现与应用
  • AOE网与关键路径 在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,边上的权值表示活动持续的时间,称这样的有向图为边表示活动的网,简称 AOE网(activity on edge network)。AOE网中没有入边的...
  • 图-关键路径算法

    2020-08-17 13:49:08
    关键路径(CriticalPath) 我们把路径上各个活动所持续时间之和称为路径长度,从源点到汇点具有最大长度的路径叫关键路径,在关键路径上的活动叫做关键活动.。 AOV网和AOE网 算法用到的4个关键变量: **etv ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,763
精华内容 705
关键字:

关键路径算法