事件最早发生时间

下图演示事件最早发生时间求解过程：

时间最迟发生时间

下图演示事件最晚发生时间求解过程：

事件最早发生时间：从前往后推

事件最晚发生时间：从后往前推

活动的最早，最晚开始时间

下图演示活动最早，最晚发生时间求解过程：

活动最早发生时间等于事件最早发生时间

活动最晚发生时间等于事件最晚发生时间减去活动所需要的时间

关键路径：活动最早开始时间=活动最晚开始时间

提高效率

关键路径算法伪代码

实例：

#include<iostream>
using namespace std;
#define Max 10//顶点最多十个
#include<stack>
//邻接表：
//边表结构体
struct edgeList
{
	int adjvex;
	int weight;
	edgeList* next;
};
//顶点表结构体
typedef struct vertexList
{
	int in;//顶点的入度
	int vertex;
	edgeList* firstedge;
}vertex[Max];
//图类
class Graph 
{
private:
	vertex ver;//顶点结构体数组
	int verNum;//顶点个数
	int edgeNum;//边的个数
	int etv[Max];//事件最早发生时间
	int ltv[Max];//事件最晚发生时间
public:
	Graph(int v[], int n, int e)
	{
		verNum = n;
		edgeNum = e;
		for (int i = 0; i < verNum; i++)
		{
			ver[i].vertex = v[i];
			ver[i].firstedge = NULL;
			ver[i].in = 0;
		}
		//用户输入边的信息
		int vi, vj,wei;
		for (int i = 0; i < edgeNum; i++)
		{
			cin >> vi >> vj>>wei;
			edgeList* edgeNode = new edgeList();
			edgeNode->adjvex = vj;
			edgeNode->weight = wei;
			//头插法
			edgeNode->next = ver[vi].firstedge;
			ver[vi].firstedge = edgeNode;
		}
		//计算入度
		for (int i = 0; i < verNum; i++)
		{
			for (int j = 0; j < verNum; j++)
			{
				edgeList* edg = ver[j].firstedge;
				while (edg)
				{
					if (edg->adjvex == i)
						ver[i].in++;
					edg = edg->next;
				}
			}
		 }
		//初始化事件最早发生时间数组
		for (int i = 0; i < verNum; i++)
		{
			etv[i] = 0;//初始化为0
		}

	}
	void display()
	{
		//打印事件开始最早时间数组
		cout << "事件最早开始时间打印：" << endl;
		for (int i = 0; i < verNum; i++)
		{
			cout << etv[i] << " ";
		}
		cout << endl;
		//打印事件开始最晚时间数组
		cout << "事件最晚开始时间打印：" << endl;
		for (int i = 0; i < verNum; i++)
		{
			cout << ltv[i] << " ";
		}
		cout << endl;
	}
	//拓扑序列
	void TopologicalSort()
	{
		//初始化栈
		stack<vertexList> st;
		//累加器
		int count = 0;
		//扫描顶点表，把没有前驱的顶点入栈
		for (int i = 0; i < verNum; i++)
		{
			if (ver[i].in == 0)
			{
				st.push(ver[i]);
				//防止重复入栈
				ver[i].in--;
			}
		}
		while (!st.empty())
		{
			vertexList temp = st.top();
			st.pop();
			cout << temp.vertex << " ";
			count++;
			edgeList* move = temp.firstedge;
			while (move)
			{
				//计算时间最早发生时间
				if (etv[temp.vertex] + move->weight > etv[move->adjvex])
				{
					etv[move->adjvex] = etv[temp.vertex] + move->weight;
				}
				//----------------------------------------------------------------
				ver[move->adjvex].in--;
				if (ver[move->adjvex].in == 0)
				{
					st.push(ver[move->adjvex]);
					ver[move->adjvex].in = -1;
				}
				move = move->next;
			}
		}
		cout << endl;
		if (count < verNum)
		{
			cout << "有回路" << endl;
		}
	}
	//求关键路径
	void CriticalPath()
	{
		//初始化事件最晚发生时间数组
		for (int i = 0; i < verNum; i++)
		{
			ltv[i] = etv[verNum-1];//事件最晚发生时间一开始都初始化为尾节点的最早发生时间，因为汇点的最晚和最早发生时间一致
		}
		//最晚发生时间=后一个节点的最晚发生时间-权值
		//邻接点的最晚发生时间减去权值，得到当前顶点的最晚发生时间
		for (int i = verNum - 1; i >= 0; i--)
		{
			edgeList* move = ver[i].firstedge;
			while (move)
			{
				ltv[i] = (ltv[move->adjvex] - move->weight) < ltv[i] ? (ltv[move->adjvex] - move->weight) : ltv[i];
				move = move->next;
			}
		}
		display();
		//活动最晚发生时间和活动最早发生时间和关键路径求解
		cout << "输出关键路径：" << endl;
		for (int i = 0; i < verNum; i++)
		{
			for (edgeList* e = ver[i].firstedge; e; e = e->next)
			{
				//活动最早发生时间等于事件最早发生时间
				int ete = etv[i];
				//活动最迟发生时间等于后一个事件最晚发生时间减去活动需要时间（权值）
				//从后往前求
				int lte = ltv[e->adjvex] - e->weight;
				//如果活动最早发生时间和活动最晚发生时间一致，表明为关键路径
				if (ete == lte)
				{
					cout << "<" << i << "," << e->adjvex << ">" << e->weight << "  ";
				}
			}
		}
		cout << endl;
	}
};
void test()
{
	int v[9] = { 0,1,2,3,4,5,6,7,8};
	Graph g(v, 9, 11);
	cout << "拓扑序列: " << endl;
	g.TopologicalSort();
	g.CriticalPath();
}
int main()
{

	test();
	system("pause");
	return 0;
}