今天看的关键路径，总结一下学的关键路径。
一，什么是关键路径
把开始顶点到完成顶点的最长路径称为关键路径。
二，如何求关键路径
（首先先说明，作为一个有关键路径的图，图中的每条边带有权值，这些权值假设为活动持续的时间，顶点表示一个活动的开始或者结束这样一个事件）。
1，作为一个关键路径，需要用到的第一个函数是拓补排序的函数，并且作为一个图如果它有关键路径，那么它不能出现回路，所以，拓补排序中要判断，如果出现回路就不用判断关键路径。
2.在拓补排序完成之后，会有一个数组x[n]按顺序存储入度为0的点，用这些点先求出与之相邻的顶点的最早时间，用数组ee[n]存储，其中，假设ee[i]与ee[j]相关联，那么ee[j]=max(ee[i]+Map[i][j]);其中二维数组map存储的从i到j的边的权值。
3.ee[n]求出之后，需要求出每个活动最晚开始时间（但是这个时间不能耽误下一个活动的开始），这个时间需要从后往前求，因为最后一位的时间是确定的。
4.当最晚时间与最早时间求出之后，关键路径的点就是最晚时间与最早时间相等的点，只需要进行判断输出即可。
下面是自己写的代码，没有结构体啥的，所以显得有些乱。。。。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int Map[110][110]; int indegree[110]; int x[110]; int value[110]; int n; int Findnum(int top) { int cnt=0; while(top!=-1) { int p=top; top=indegree[top]; x[cnt++]=p; for (int i=1;i<=n;++i) { if (Map[p][i]!=0) { value[i]-=1; if(value[i]==0) { indegree[i]=top; top=i; } } } } if (cnt<n)return 0; return 1; } int tobosort() { memset(indegree,0,sizeof(indegree)); memset(x,0,sizeof(x)); int top=-1; for (int i=1;i<=n;++i) { if (value[i]==0) { indegree[i]=top; top=i; } } int nd=0; nd=Findnum(top); if(nd==0)return 0; return 1; }//以上两个函数是用来求拓补排序的 void getee(int *ee) { memset(ee,0,sizeof(int)*100); for (int i=0;i<n;++i) { int k=x[i]; for (int j=1;j<=n;j++) { if (Map[k][j]!=0&&ee[j]<ee[k]+Map[k][j]) { ee[j]=ee[k]+Map[k][j]; } } } }//求最早的时间 void getll(int * ee,int * ll) { for (int i=1;i<=n;++i) { ll[i]=ee[x[n-1]]; } for (int i=n-1;i>=1;--i) { int k=x[i]; for (int j=1;j<=n;++j) { if (Map[k][j]!=0&&ll[k]>ll[j]-Map[k][j]) { ll[k]=ll[j]-Map[k][j]; } } } }//求最晚的时间 int guanjian() { int ee[110]; int ll[110]; if (tobosort()==0) return 0; getee(ee); for(int i=1;i<=n;++i) { cout<<ee[i]<<" "; } cout<<endl; getll(ee,ll); for (int i=1;i<=n;++i) { cout<<ll[i]<<" "; } cout<<endl; for (int i=1;i<=n;++i) { for (int j=1;j<=n;++j) { if (ee[i]==(ll[j]-Map[i][j])&&Map[i][j]!=0) { cout<<"关键路径为"<<i<<" "<<j<<endl; } } } return 1; }//求关键路径的函数
