精华内容
下载资源
问答
  • AOE-网如下: 把图中的AOE-网看作一个工程的话,则就需要解决下面两...要估算整项工程完成的最短时间,就是要找一条从源点到汇点的带权路径最长的路径,称为关键路径关键路径上的活动叫做关键活动,这些活动是...

    AOE-网如下:

    把图中的AOE-网看作一个工程的话,则就需要解决下面两个问题:

    • 估算完成整项工程至少需要多少时间
    • 判断哪些活动是影响工程进度的关键

    分析

         整个工程只有一个开始点和一个完成点,所以在正常的情况(无环)下,网中只有一个入度为零的点,称为源点,也只有一个出度为零的点,称为汇点。在整个AOE-网中,一条路径各弧上的权值之和称为该路径的带权路径长度。要估算整项工程完成的最短时间,就是要找一条从源点到汇点的带权路径最长的路径,称为关键路径。关键路径上的活动叫做关键活动,这些活动是影响工程进度的关键,他们提前或拖延将使整个工程提前或拖延。

    确定关键路径

    一,定义4个描述量

    1,事件N的最早发生时间ve[N的下标]

    进入事件N的每一活动都结束,N才能发生,所以ve[N的下标]是从源点到N的最长路径长度

    2,事件N的最迟发生时间vl[N的下标]

    事件N的发生不得延迟于N的每一后继事件的最迟发生时间。

    为了不拖延工期,N的最迟发生时间不得迟于其后继事件M的最迟发生事件减去N到M的持续时间

    eg:若N是B,M是E;则N的最迟发生时间不得迟于M的最迟发生时间减去MN之间的时间1.

    3,活动的最早开始时间e[]

    只有事件N发生了,活动x才能发生,所以,活动x的最早开始时间等于事件N的最早发生事件ve[N的下标]

    eg:若N是B,x是代表BE这条弧,则只有事件B发生了,活动BE才能发生

    4,活动的最晚开始时间l[]

    活动x的开始事件需保证不延误事件N的最迟发生时间。所以,活动x的最晚开始时间等于事件N的最迟发生时间vl[N的下标]减去活动x持续的时间

    eg:若N是E,x是代表BE这条弧,则BE不能厌恶N的发生,所以最晚开始时间等于vl[N]-BE;

    二,关键路径求解过程

    1. 对图中顶点进行排序,在排序过程中按照拓扑序列求出每个事件的最早发生时间ve[];
    2. 按照逆拓扑排序求出每个事件的最迟发生时间vl[];
    3. 求出每个活动XY的最早开始时间e[];
    4. 求出每个活动XV的最晚开始时间l[];
    5. 如果e[i]=l[i],即为关键活动。由关键活动形成的由源点到汇点的每一条路径就是关键路径,关键路径可能不止一条

    三,关键路径部分求解代码

    int ve[pointMax];      //最早发生时间
    int vl[pointMax];      //最晚发生时间
    
    void CritPath(ATgroup *A)
    {
    	int n = A->point;          //n为顶点个数
    	for (int i = 0; i < n; i++)        //将每个事件的最早事件为0
    		ve[i] = 0;
    
    	//---按拓扑次序求每个事件的最早发生时间---//
    	int k, j;
    	for (int i = 0; i < n; i++)
    	{
    		k = topo[i];                 //取的拓扑排序中的顶点序号
    		cout <<"K=F"<< k << "  "<<endl;
    		VtNode *p = A->vertices[k].Out;     //指向K的第一个邻接结点
    		while (p != NULL)
    		{
    			j = p->peaceE;
    			if (ve[j] < ve[k] + p->len)
    			{
    				ve[j] = ve[k] + p->len;
    				cout << ve[j] << "  " << ve[k] << "   " << p->len << endl;
    			}
    			p = p->nextVtt;
    		}
    		cout << ve[j] << endl;
    	}
    	for (int i = 0; i < A->point; i++)
    	{
    		cout << ve[i] << "   ";
    	}
    	cout << endl;
    	cout << endl;
    
    	for (int i = 0; i < n; i++)       //初始化
    	{
    		vl[i] = ve[topo[n - 1]];
    	}
    	//---按逆拓扑排序求每个事件的最迟发生时间----//
    	for (int i = n - 1; i >= 0; i--)
    	{
    		k = topo[i];                 //取的拓扑排序中的顶点序号
    		VtNode *p = A->vertices[k].Out;     //指向K的第一个邻接结点
    		//cout << k << endl;
    		while (p != NULL)
    		{
    			j = p->peaceE;
    			if (vl[k] > vl[j] - p->len)
    			{
    				vl[k] = vl[j] - p->len;
    				//cout << vl[k] << "  " << vl[j] << "   " << p->len << endl;
    			}
    			p = p->nextVtt;
    		}
    		//cout << vl[j] << endl;
    	}
    
    	for (int i = 0; i < A->point; i++)
    	{
    		cout << vl[i] << "   ";
    	}
    	cout << endl;
    	cout << endl;
    
    	//----判断每一活动是否为关键活动-----//
    	int e, l;
    	for (int i = 0; i < n; i++)
    	{
    		VtNode *p = A->vertices[i].Out;
    		while (p != NULL)
    		{
    			j = p->peaceE;
    			e = ve[i];
    			l = vl[j] - p->len;
    			if (e == l)
    			{
    				cout << A->vertices[i].data << "   " << A->vertices[j].data << endl;
    			}
    			p = p->nextVtt;
    		}
    	}
    }

    四,整段程序代码

    #include<iostream>
    using namespace std;
    
    #define pointMax 100
    
    struct VtNode                 //权值信息
    {
    	VtNode *nextVt;           //入度链表下一个结点
    	int peace;                //入度下一顶点的值
    
    	VtNode *nextVtt;          //出度链表下一个结点
    	int peaceE;               //出度下一顶点的值
    
    	int len;
    };
    struct PoNode                  //顶点信息
    {
    	char data;
    	VtNode *firstPo;          //入度
    	VtNode *Out;              //出度
    };
    
    struct ATgroup
    {
    	PoNode vertices[pointMax];     //每一个verticse代表一个顶点
    	int point, vert;               //point顶点数,vert弧数
    };
    
    struct Node
    {
    	int data;
    	Node *next;
    };
    
    struct SqStack          //栈
    {
    	Node *base;          //栈底
    	Node *top;           //栈顶
    	int data;
    };
    
    void Push(SqStack &S, int i)       //入栈
    {
    	Node *m = new Node;
    	m->data = i;
    	m->next = S.top;             //入栈过程
    	S.top = m;
    }
    
    int Pop(SqStack &S)              //出栈
    {
    	int n = S.top->data;
    	S.top = S.top->next;         //出栈过程
    	return n;
    }
    
    
    int ATlocate(ATgroup A, char x)             //找到位置
    {
    	for (int i = 0; i < A.point; i++)       //依次遍历点的信息
    	{
    		if (A.vertices[i].data == x)        //找到x的位置
    		{
    			return i;
    		}
    	}
    }
    
    void show(ATgroup &A)                      //显示当前所有点入度出度的顶点
    {
    	//cout << endl;
    	for (int i = 0; i < A.point; i++)
    	{
    		//cout << i;
    		if (A.vertices[i].firstPo != NULL)          //入度位置
    		{
    		//	cout << "    " << A.vertices[i].firstPo->peace << "   ";
    		}
    		//else
    		//	cout << "    -1" << "    ";
    
    		if (A.vertices[i].Out != NULL)             //出度位置
    		{
    		//	cout << A.vertices[i].Out->peaceE << endl;
    		}
    		//else
    		//	cout << "    -1" << endl;
    	}
    }
    
    void CreatAT(ATgroup &A)
    {
    	cout << "输入邻接矩阵顶点数:";
    	cin >> A.point;
    	cout << "输入邻接矩阵边数:";
    	cin >> A.vert;
    	getchar();
    	char q[100];
    	cout << "输入顶点信息:";
    	gets_s(q);
    	for (int i = 0; i < A.point; i++)
    	{
    		A.vertices[i].data = q[i];               //输入顶点值
    		A.vertices[i].firstPo = NULL;            //初始化头结点为空
    		A.vertices[i].Out = NULL;
    	}
    	char v1, v2; int m, n; int len;
    	for (int i = 0; i < A.vert; i++)            //输入各边,构造邻接表
    	{
    		cout << "输入第" << i << "条边的依附的两个顶点:";
    		int Q;
    		cin >> v1 >> v2 >> Q;
    		m = ATlocate(A, v1);                  //确定位置
    		n = ATlocate(A, v2);
    		//第一个
    		VtNode *p1 = new VtNode;
    		VtNode *p2 = new VtNode;
    		p1->peace = m;                             //入度
    		p1->nextVt = A.vertices[n].firstPo;
    		A.vertices[n].firstPo = p1;
    
    		p2->peaceE = n;                            //出度
    		p2->nextVtt = A.vertices[m].Out;
    		p2->len = Q;
    		A.vertices[m].Out = p2;
    	}
    	//show(A);
    }
    
    void FindIn(ATgroup *A, int *in)           //统计所有点的入度数并存入到in数组中
    {
    	int n = 0;
    	for (int i = 0; i < A->point; i++)     //遍历每一个点
    	{
    		VtNode *p = new VtNode;
    		p = A->vertices[i].firstPo;
    		while (p != NULL)                  //将入度链表进行遍历
    		{
    			n++;
    			p = p->nextVt;          //下一结点
    		}
    		in[i] = n;          //存入in数组
    		n = 0;
    	}
    }
    
    void SHOW(int *a, ATgroup *A)           //显示当前所有顶点入度数量还有几个
    {
    	for (int i = 0; i < A->point; i++)
    	{
    		//cout << a[i] << "  ";
    	}
    	//cout << endl;
    }
    
    int M[pointMax] = { 0 };
    int topo[pointMax];           //拓扑遍历存入
    
    void TPsort(ATgroup *A, SqStack &S)           //拓扑排序过程
    {
    	int Indegree[pointMax];
    	FindIn(A, Indegree);             //将入度赋值给数组
    
    	for (int i = 0; i < A->point; i++)
    	{
    		if (Indegree[i] == 0)         //将所有入度等于0的入栈
    		{
    			//cout << "Push=" << i << endl;
    			Push(S, i);
    		}
    	}
    
    	int m = 0;                //统计入度的顶点数
    	int n, k;
    
    	while (S.base != S.top)       //判断是否遍历完
    	{
    		//cout << endl;
    		n = Pop(S);         //栈顶出栈
    		//cout << "Pop=" << n << endl;
    		topo[m] = n;        //存入topo
    		m++;
    		VtNode* p = new VtNode;
    		p = A->vertices[n].Out;             //出度链表的结点
    		while (p != NULL)            //遍历出度链表
    		{
    			k = p->peaceE;          //某结点的位置
    			//cout << "出度下一结点k=" << k << endl;
    			Indegree[k]--;          //将该结点顶点位置入度减一
    			//SHOW(Indegree, A);       //显示当前所有点的入度
    			if (Indegree[k] == 0)      //当等于0时,入栈
    			{
    				//cout << "Push=" << k << endl;
    				Push(S, k);
    			}
    			p = p->nextVtt;     //下一个
    		}
    	}
    }
    
    
    
    int ve[pointMax];      //最早发生时间
    int vl[pointMax];      //最晚发生时间
    
    void CritPath(ATgroup *A)
    {
    	int n = A->point;          //n为顶点个数
    	for (int i = 0; i < n; i++)        //将每个事件的最早事件为0
    		ve[i] = 0;
    
    	//---按拓扑次序求每个事件的最早发生时间---//
    	int k, j;
    	for (int i = 0; i < n; i++)
    	{
    		k = topo[i];                 //取的拓扑排序中的顶点序号
    		cout <<"K=F"<< k << "  "<<endl;
    		VtNode *p = A->vertices[k].Out;     //指向K的第一个邻接结点
    		while (p != NULL)
    		{
    			j = p->peaceE;
    			if (ve[j] < ve[k] + p->len)
    			{
    				ve[j] = ve[k] + p->len;
    				cout << ve[j] << "  " << ve[k] << "   " << p->len << endl;
    			}
    			p = p->nextVtt;
    		}
    		cout << ve[j] << endl;
    	}
    	for (int i = 0; i < A->point; i++)
    	{
    		cout << ve[i] << "   ";
    	}
    	cout << endl;
    	cout << endl;
    
    	for (int i = 0; i < n; i++)       //初始化
    	{
    		vl[i] = ve[topo[n - 1]];
    	}
    	//---按逆拓扑排序求每个事件的最迟发生时间----//
    	for (int i = n - 1; i >= 0; i--)
    	{
    		k = topo[i];                 //取的拓扑排序中的顶点序号
    		VtNode *p = A->vertices[k].Out;     //指向K的第一个邻接结点
    		//cout << k << endl;
    		while (p != NULL)
    		{
    			j = p->peaceE;
    			if (vl[k] > vl[j] - p->len)
    			{
    				vl[k] = vl[j] - p->len;
    				//cout << vl[k] << "  " << vl[j] << "   " << p->len << endl;
    			}
    			p = p->nextVtt;
    		}
    		//cout << vl[j] << endl;
    	}
    
    	for (int i = 0; i < A->point; i++)
    	{
    		cout << vl[i] << "   ";
    	}
    	cout << endl;
    	cout << endl;
    
    	//----判断每一活动是否为关键活动-----//
    	int e, l;
    	for (int i = 0; i < n; i++)
    	{
    		VtNode *p = A->vertices[i].Out;
    		while (p != NULL)
    		{
    			j = p->peaceE;
    			e = ve[i];
    			l = vl[j] - p->len;
    			if (e == l)
    			{
    				cout << A->vertices[i].data << "   " << A->vertices[j].data << endl;
    			}
    			p = p->nextVtt;
    		}
    	}
    }
    
    int main()
    {
    	ATgroup *A = new ATgroup;
    	SqStack *S = new SqStack;
    	S->top = S->base;
    	S->data = pointMax;
    	CreatAT(*A);
    	TPsort(A, *S);
    	CritPath(A);
    	system("pause");
    }

     

     

    展开全文
  • 关键路径

    2019-12-29 20:09:34
    AOV网的关键路径 ...关键路径长度就是整个工程所需最短工期,关键路径活动称为关键活动。 事件最早发生时间 ve[k]是指k发生最早时间,它值是从源点到顶点k最长路径。 这个时间决定了...

    AOV网的关键路径

    由于AOV网中的某些活动能够同时进行,固完成整个工程所必须花费的时间应该为源点到终点的最大路径长度
    (这里指的长度是指该路径上的各个活动所需的时间之和)。从源点到终点的最大路径长度的路径称为关键路径,
    关键路径长度就是整个工程所需的最短工期,关键路径上的活动称为关键活动。
    
    事件的最早发生时间
    ve[k]是指k发生的最早的时间,它的值是从源点到顶点k的最长路径。
    这个时间决定了所有从顶点k发出的有向边所代表的活动能够开工的最早的时间。
    
    事件的最迟发生时间
    	vl[k]是指在不推迟整个工期的前提下,时间vk允许的最晚发生时间。
    
    活动ai的最早开始时间
    	若活动ai是由<vk,vj>弧来表示的,则只有时间vk发生了,
    	ai才能发生,所以ai的最早开始时间就是vk的最早发生时间
    
    活动ai的最晚开始时间
    	活动ai的最晚开始时间是指在不推迟整个工程完成日期的前提下,必须开始的最晚时间。
    

    当活动的最早开始时间等于其最晚开始时间的时候,可判定该活动为关键活动

    展开全文
  • 关键路径确定过程

    2020-02-13 16:38:41
    关键路径的确定 从源点到汇点具有最大路径长度的路径称为关键路径。关键路径长度就是整个工程所需的最短工期,关键路径上的活动为关键活动,要缩短整个工期,必须加快关键活动的进度。 步骤 事件的最早发生时间ve...

    关键路径的确定

    在这里插入图片描述
    从源点到汇点具有最大路径长度的路径称为关键路径。关键路径长度就是整个工程所需的最短工期,关键路径上的活动为关键活动,要缩短整个工期,必须加快关键活动的进度。

    步骤

    1. 事件的最早发生时间ve[k]
      顺拓扑序列求,ve[i]=max{紧挨权值+ve[到此点前一点]},即5->8权值为3,6->8权值为5,则ve[8]=max{ve[5]+3,ve[6]+5}
    2. 事件的最迟发生时间vl[k]
      逆拓扑序列求,vl[i]=min{vl[它到的下一点]-紧挨权值},vl[最后一点]=ve[最后一点]
    3. 活动ai的最早开始时间e[i]
      ai假设是从k到j,则e[i]=ve[j]
    4. 活动ai的最晚开始时间l[k]
      ai假设是从i到j,则l[i]=vl[k]-ai的权值

    当活动ai的最早开始时间=最晚开始时间,则该路径在关键路径上。

    上面有一例子:
    可求得
    事件的最早发生时间

    ve[0]=0
    ve[1]=3
    ve[2]=4
    ve[3]=5
    ve[4]=7
    ve[5]=9
    ve[6]=15
    ve[7]=11
    ve[8]=21
    ve[9]=22
    ve[10]=28

    事件的最迟发生时间

    vl[10]=28
    vl[9]=22
    vl[8]=21
    vl[7]=11
    vl[6]=21
    vl[5]=19
    vl[4]=7
    vl[3]=15
    vl[2]=4
    vl[1]=6
    vl[0]=0

    再求活动ai的最早开始时间与最晚开始时间

    e[1]=0 ~~ ~~ l[1]=3
    e[2]=0 ~~ ~~ l[2]=0 *
    e[3]=3 ~~ ~~ l[3]=13
    e[4]=3 ~~ ~~ l[4]=6
    e[5]=4 ~~ ~~ l[5]=4 *
    e[6]=4 ~~ ~~ l[6]=14
    e[7]=5 ~~ ~~ l[7]=15
    e[8]=7 ~~ ~~ l[8]=13
    e[9]=7 ~~ ~~ l[9]=7 *
    e[10]=9 ~~ ~~ l[10]=19
    e[11]=15 ~~ ~~ l[11]=21
    e[12]=11 ~~ ~~ l[12]=18
    e[13]=11 ~~ ~~ l[13]=11 *
    e[14]=21 ~~ ~~ l[14]=21 *
    e[15]=22 ~~ ~~ l[15]=22 *

    所以关键路径是v0->v2->v4->v7->v8->v9->v10
    当然过程应该更复杂的,我只写了得数。

    展开全文
  • 要估算整项工程完成最短时间, 就是要找一条从源点到 汇点带权路径长度最长路径, 称为关键路径 (Critical Path)。关键路径 活动叫做关键活动,这些活动是影响工程进度关键, 它们提前或拖延将使整个...

    AOE-网:

    AOE-网 (Activity On Edge) , 即以边表示活动的网。 AOE-网是一个带权的有向无环图, 其中顶点表示事件, 弧表示活动, 权表示活动持续的时间。

    关键路径:

    要估算整项工程完成的最短时间, 就是要找一条从源点到 汇点的带权路径长度最长的路径, 称为关键路径 (Critical Path)。关键路径上的 活动叫做关键活动,这些活动是影响工程进度的关键, 它们的提前或拖延将使整个工程提前或拖延。
    在这里插入图片描述
    其关键路径为:
    在这里插入图片描述
    关键路径有两条: (v0, v1,v4,v6, v8)或(v0, v1,v4,v7,v8), 长度均为18。关键活动为(a1, a4, a7, a10)或(a1, a4, a8, a11)。

    4个描述量:

    1,事件v的最早发生时间ve(i):ve(i) = Max{ve(k) + W(i,k)}
    2,事件v的最迟发生时间vl(i):vl(i) = Min{vl(k) - W(k,i)}
    根据前两个可求得后两个:
    3,活动a的最早开始时间e(i):e(i) = ve(j)
    4,活动a的最晚开始时间l(i) :l(i) = vl(k) - (ai的持续时间)

    找出 e(i)=i(i)的活动a, 即为关键活动。由关键活动形成的由源点到汇点的每一条路径 就是关键路径,关键路径有可能不止一条。
    在这里插入图片描述

    以上图为例:

    代码如下:

    #include<stdio.h>
    
    #define MVNum 100
    typedef char OtherInfo;
    typedef char VerTexType;
    
    //图的邻接表存储结构
    typedef struct ArcNode			//边结点
    {
    	int adjvex;//邻接点域 
    	struct ArcNode *nextarc;//链域
    	OtherInfo info;//数据域
    	int weight;	//权值
    }ArcNode;
    typedef struct VNode			//顶点信息
    {
    	VerTexType data;//数据域
    	ArcNode *firstarc;//链域
    }VNode, AdjList[MVNum];
    typedef struct                  //邻接表
    {
    	AdjList vertices;
    	int vexnum, arcnum;
    }ALGraph;
    
    //函数声明
    int LocateVex(ALGraph G, char v);
    void LinkAL(ALGraph &G, int i, int j, int weight);
    void FindInDegree(ALGraph G, int indegree[]);
    void printTopo(int topo[], int m);
    
    
    //邻接表创建有向图
    void CreateUDG(ALGraph &G)
    {
    	G.vexnum = 9;						//输入总顶点数和边数
    	G.arcnum = 11;
    	G.vertices[0].data = 'v0';			//输入顶点信息
    	G.vertices[0].firstarc = NULL;
    	G.vertices[1].data = 'v1';
    	G.vertices[1].firstarc = NULL;
    	G.vertices[2].data = 'v2';
    	G.vertices[2].firstarc = NULL;
    	G.vertices[3].data = 'v3';
    	G.vertices[3].firstarc = NULL;
    	G.vertices[4].data = 'v4';
    	G.vertices[4].firstarc = NULL;
    	G.vertices[5].data = 'v5';
    	G.vertices[5].firstarc = NULL;
    	G.vertices[6].data = 'v6';
    	G.vertices[6].firstarc = NULL;
    	G.vertices[7].data = 'v7';
    	G.vertices[7].firstarc = NULL;
    	G.vertices[8].data = 'v8';
    	G.vertices[8].firstarc = NULL;
    
    	int i, j;							//输入边信息
    	i = LocateVex(G, 'v0');
    	j = LocateVex(G, 'v1');
    	LinkAL(G, i, j, 6);
    	i = LocateVex(G, 'v0');
    	j = LocateVex(G, 'v2');
    	LinkAL(G, i, j, 4);
    	i = LocateVex(G, 'v0');
    	j = LocateVex(G, 'v3');
    	LinkAL(G, i, j, 5);
    	i = LocateVex(G, 'v1');
    	j = LocateVex(G, 'v4');
    	LinkAL(G, i, j, 1);
    	i = LocateVex(G, 'v2');
    	j = LocateVex(G, 'v4');
    	LinkAL(G, i, j, 1);
    	i = LocateVex(G, 'v3');
    	j = LocateVex(G, 'v5');
    	LinkAL(G, i, j, 2);
    	i = LocateVex(G, 'v4');
    	j = LocateVex(G, 'v6');
    	LinkAL(G, i, j, 9);
    	i = LocateVex(G, 'v4');
    	j = LocateVex(G, 'v7');
    	LinkAL(G, i, j, 7);
    	i = LocateVex(G, 'v5');
    	j = LocateVex(G, 'v7');
    	LinkAL(G, i, j, 4);
    	i = LocateVex(G, 'v6');
    	j = LocateVex(G, 'v8');
    	LinkAL(G, i, j, 2);
    	i = LocateVex(G, 'v7');
    	j = LocateVex(G, 'v8');
    	LinkAL(G, i, j, 4);
    }
    
    //建立边
    void LinkAL(ALGraph &G, int i, int j, int weight)
    {
    
    	ArcNode *p1;
    	p1 = new ArcNode;
    	p1->adjvex = j;
    	p1->nextarc = G.vertices[i].firstarc;						  //头插法
    	G.vertices[i].firstarc = p1;
    
    	p1->weight = weight;
    }
    
    //返回顶点位置下标
    int LocateVex(ALGraph G, char v)
    {
    	for (int i = 0; i < G.vexnum; i++)
    	{
    		if (G.vertices[i].data == v)
    		{
    			return i;
    		}
    	}
    }
    
    //打印输出图
    void printGraph(ALGraph G)
    {
    	for (int i = 0; i < G.vexnum; i++)
    	{
    		printf("%d :", i);
    		printf("v%d ->", i);
    
    		ArcNode *p;
    		p = G.vertices[i].firstarc;
    		while (p != NULL)
    		{
    			printf("%d->", p->adjvex);
    			p = p->nextarc;
    		}
    		printf("\n");
    	}
    }
    
    //邻接表深度优先遍历
    bool visited[MVNum];
    void DFS_AL(ALGraph G, int v)
    {
    	printf("v%c->", G.vertices[v].data);
    	visited[v] = true;
    	ArcNode *p;
    	p = G.vertices[v].firstarc;
    	while (p != NULL)
    	{
    		int w = p->adjvex;
    		if (!visited[w])
    		{
    			DFS_AL(G, w);
    		}
    		p = p->nextarc;
    	}
    }
    
    
    
    //定义栈
    #define MAXSIZE 100
    typedef struct
    {
    	int base[MAXSIZE];
    	int *top;
    	int stacksize;
    }SqStack;
    //初始化
    int InitStack(SqStack &S)
    {
    	S.top = S.base;
    	S.stacksize = MAXSIZE;
    	return 1;
    }
    //入栈
    int Push(SqStack &S, int e)
    {
    	if (S.top - S.base == S.stacksize) return 0;
    	*S.top++ = e;
    	return 1;
    }
    //出栈
    int Pop(SqStack &S, int &e)
    {
    	if (S.top == S.base) return 0;
    	e = *--S.top;
    	return 1;
    }
    
    
    //拓扑排序
    int indegree[MVNum];		//存放各顶点入度
    int topo[MVNum];			//存放拓扑序列的顶点序号
    SqStack S;					//暂存入度为0的顶点
    int TopologicalSort(ALGraph G, int topo[])
    {
    	ArcNode *p;
    	int i, m = 0;				//m用来计数
    	FindInDegree(G, indegree);	//求各顶点的入度存入indegree数组
    	InitStack(S);
    	for (i = 0; i < G.vexnum; i++)
    	{
    		if (!indegree[i])
    		{
    			Push(S, i);			//入度为0的入栈
    		}
    	}
    
    	while (S.base != S.top)
    	{
    		Pop(S, i);
    		topo[m] = i;		//入度为0的出栈并存入topo数组中
    		m++;				//计数加一
    		p = G.vertices[i].firstarc;		//p指向后继边结点
    		while (p != NULL)
    		{
    			int k = p->adjvex;			//k为顶点下标值
    			--indegree[k];				//顶点的入度减1来代替删除边的操作
    			if (indegree[k] == 0)		//如果减1后为0 则入栈
    			{
    				Push(S, k);
    			}
    			p = p->nextarc;				//继续下一个后继边结点
    		}
    	}
    
    	if (m < G.vexnum)  return 0;		//输出的顶点数小千有向图中的顶点数,则说明有向图中存在环
    	else return m;						//否则投拓扑排序成功,无环
    }
    
    //求各顶点的入度
    void FindInDegree(ALGraph G, int indegree[])
    {
    	//初始化
    	for (int i = 0; i < G.vexnum; i++)
    	{
    		indegree[i] = 0;
    	}
    
    	ArcNode *p;
    	//遍历整个邻接表求出入度
    	for (int j = 0; j < G.vexnum; j++)
    	{
    		p = G.vertices[j].firstarc;
    		while (p != NULL)
    		{
    			indegree[p->adjvex]++;
    			p = p->nextarc;
    		}
    	}
    }
    
    //打印拓扑序列
    void printTopo(int topo[], int m)
    {
    	printf("\n该图的一个拓扑序列为:");
    	for (int i = 0; i < m; i++)
    	{
    		printf("v%d->", topo[i]);
    	}
    }
    
    
    //关键路径算法
    int ve[MVNum];				//事件最早发生时间
    int vl[MVNum];				//事件最晚发生时间
    int CriticalPath(ALGraph G)
    {
    	//初始化最早发生时间为最小
    	int n, i;
    	if (!TopologicalSort(G, topo))   return 0;		//拓扑排序失败,有环!
    	n = G.vexnum;
    	for (i = 0; i < n; i++)
    	{
    		ve[i] = 0;
    	}
    
    	//求每个事件最早发生时间
    	ArcNode *p;
    	int k, j;
    	for (i = 0; i < n; i++)
    	{
    		k = topo[i];
    		p = G.vertices[k].firstarc;
    		while (p != NULL)
    		{
    			j = p->adjvex;
    			if (ve[j]<ve[k] + p->weight)		//更新顶点的最早方式时间即最大的weight活动
    			{
    				ve[j] = ve[k] + p->weight;		//第一个顶点的最早发生时间ve[0]==0;
    			}
    			p = p->nextarc;
    		}
    	}
    
    	//初始化最晚发生时间为最大
    	for (i = 0; i < n; i++)
    	{
    		vl[i] = ve[n - 1];
    	}
    
    	//逆拓扑排序求最迟发生时间
    	for (i = n - 1; i >= 0; i--)				//从倒数第二个顶点开始
    	{
    		k = topo[i];
    		p = G.vertices[k].firstarc;
    		while (p != NULL)
    		{
    			j = p->adjvex;
    			if (vl[k]>vl[j] - p->weight)
    			{
    				vl[k] = vl[j] - p->weight;
    			}
    			p = p->nextarc;
    		}
    	}
    
    
    	//判断是否为关键路径
    	printf("\n关键路径为:");
    	int e, l;
    	for (i = 0; i < n; i++)
    	{
    		p = G.vertices[i].firstarc;
    		while (p != NULL)
    		{
    			j = p->adjvex;
    			e = ve[i];
    			l = vl[j] - p->weight;
    			if (e == l)		//相等则为关键活动,输出对应的关键路径
    			{
    				printf("\nv%c->v%c ", G.vertices[i].data, G.vertices[j].data);
    			}
    			p = p->nextarc;
    		}
    	}
    }
    
    
    int main()
    {
    	ALGraph G;
    	CreateUDG(G);
    
    	printGraph(G);
    
    	int v = 0;
    	printf("深度优先遍历:");
    	DFS_AL(G, v);
    
    	//拓扑排序
    	printf("\n==========================\n");
    	int loop = TopologicalSort(G, topo);
    	if (loop == 0)
    	{
    		printf("\n拓扑排序失败,该图有环!\n");
    	}
    	else
    	{
    		printf("\n拓扑排序成功,该图无环!");
    		printTopo(topo, loop);		//输出拓扑序列
    	}
    
    	//关键路径
    	CriticalPath(G);
    	//输出ve[]和vl[]数组
    	printf("\nve[]:");
    	for (int i = 0; i <G.vexnum; i++)
    	{
    		printf("%d,", ve[i]);
    	}
    	printf("\nvl[]:");
    	for (int i = 0; i <G.vexnum; i++)
    	{
    		printf("%d,", vl[i]);
    	}
    }
    

    运行结果:

    在这里插入图片描述

    展开全文
  • C语言关键路径实现

    千次阅读 2017-01-22 11:07:57
    确定关键路径的四个描述量: 1. 事件vi的最早发生时间ve(i): 进入世界vi的每一活动都结束,vi才有可发生,所以ve(i)是从源点到vi的最长路径长度。其中v0一般为0. 2. 事件vi的最迟发生时间: 事件vi的发生不得...
  • AOE 网中的活动可以并行,只要活动的前提状态得到满足,...完成整个工程的最短时间就是从开始顶点到完成顶点的最长路径长度(路径上各边的权值之和) 从开始顶点到完成顶点的最长路径称为关键路径。 复杂度 O(v+e)
  • 求AOE-网的关键路径并打印

    千次阅读 2016-10-04 12:10:12
    AOE-网就是用弧表示活动,是一种带权重的有向无环图,其中,顶点表示事件,弧表示活动,...由于AOE网中有些活动可以并行进行,故完成工程的最短时间是从开始点到完成点的最长路径的长度。 这里我们要特别注意节点与弧
  • 关键路径法及C语言实现

    千次阅读 2019-03-26 18:56:30
    AOE网是以边表示活动的有向无环网,在AOE网中,具有最大路径长度的路径称为关键路径关键路径表示完成工程的最短工期。 下图 1 表示 AOE网: 如图 1 所示就是一个 AOE 网,例如 a1=6 表示完成 a1 活动完成需要 6 ...
  • 一个工程所需的最短时间 就是 完成从开始顶点到终止顶点的最长路径的长度。 2、关键路径关键路径就是从开始顶点到结束顶点之间 一条具有最长路径长度的路径。关键路径可能不止一条。 3、活动的early...
  • /*18747 最长路径 时间限制:1000MS 代码长度限制:10KB ...请你计算出这个项目最早完成事件,也就是起点到收点最长路径。 输入格式 第一行两个整数n和m,代表结点数量和边数量。(1<=n,m<=1.
  • 关键路径 --->图

    2016-07-06 13:12:52
    AOE网:在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续事件,这种有向图的边表示活动的网,我们称之为AOE...红线就是关键路径,并且长度为5.5天。 关键路径就是权值加
  • 以缩短工期, 我们必须找出影响工程进度的关键活动, 这就是关键路径的求解问题。 给出下图,关键路径为:v1v2v5v7v9、v1v2v5v8v9, 其长度为。 写出求出该图的关键路径的算法。*/ #include #include #include #include ...
  • bzoj3611:[Heoi2014]大工程

    2019-03-26 10:00:00
    传送门 显然还是虚树,虚树之后树形dp ...就是每次对于当前走到节点记一下它子树里深度最深和深度最浅的关键点,以及深度和,然后考虑经过当前点的路径长度,更新就好了 然后还需要统计答案,所...
  • 大小与线的长度、流过的电流大小以及频率成正比);而如果信号不能通过尽可能小的环路 返回,就可能形成一个大的环状天线(注:小型环状天线的辐射大小与环路面积、流过环路 的电流大小以及频率的平方成正比)。在设计...
  • 遇到这种移动问题,我们可以尝试先给出最终需要的长度,然后从后向前扫描,同时给定两个指针来保证定位。逆向思维 面试题5:从头到尾打印链表:从头到尾遍历链表,并用一个栈存储每个结点的值,之后出栈输出值即可。...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    4、用邻接矩阵或邻接图实现一个有向图存储,并实现单源最短路径算法实现(这个类一个成员函数),并能输出该图的关键路径。 注:1、要用面向对象方法设计代码; 2、一个图是一个类实例; 3、类...
  • 习题1-11在上题的分组交换网中,设报文长度和分组长度分别为x和(p+h)(bit),其中p为分组的数据部分的长度,而h为每个分组所带的控制信息固定长度,与p的大小无关。通信的两端共经过k段链路。链路的数据率为b...
  • 应用案例 - 用户身份验证 / 英制单位与公制单位互换 / 掷骰子决定做什么 / 百分制成绩转等级制 / 分段函数求值 / 输入三条边的长度如果能构成三角形就计算周长和面积 Day04 - 循环结构 循环结构的应用场景 - ...
  • 他参与本书编写就是为了帮助别人实现这一目标。 目录 封面 -11 封底 -10 扉页 -9 版权 -8 版权声明 -7 致谢 -6 目录 -5 第1章 SQL核心 1 1.1 SQL语言 1 1.2 数据库接口 2 1.3 SQL*Plus 回顾 3 1.3.1 连接到...
  • 他参与本书编写就是为了帮助别人实现这一目标。 目录 封面 -11 封底 -10 扉页 -9 版权 -8 版权声明 -7 致谢 -6 目录 -5 第1章 SQL核心 1 1.1 SQL语言 1 1.2 数据库接口 2 1.3 SQL*Plus 回顾 3 1.3.1 连接到...
  • 它与高可用性解决方案之间差异在于所防止故障类型以及通常认为合理时间长度。HA 故障转移通常以秒和分钟来衡量,而灾难恢复则可能以小时和天来进行衡量。不过并非总是这样,但这个差异区分了对这些解决方案...
  • vc++ 开发实例源码包

    2014-12-16 11:25:17
    1) 客户向服务器发送请求, 每个请求的长度不定. 请求的长度在第一个INT中指定. 2) 每个服务器通常会向多种客户提供服务, 例如, TS要同时向CP, NP提供服务, CP要向NP和其他CP提供服务, 同时还是其他CP, TS, SP的客户....

空空如也

空空如也

1 2
收藏数 33
精华内容 13
关键字:

关键路径的长度就是工程的