关键路径的求法一般是针对有向无环图的，常用来解决工程中的问题，前面我们学过Bellman和SPFA算法，如果我们给每条边变成相反数就可以求解关键路径了，当然关键路径不止一种求法，数据结构中给出的关键路径求法的优势在于其更快，利用了ve，vl数组，下面是其代码。
#include<iostream> #include<stack> #include<queue> #include<vector> #include<algorithm> using namespace std; const int maxv=1001; struct node{ int v,w; }; vector<node>Adj[maxv];//定义邻接表 int indegree[maxv];//存储入度 int ve[maxv],vl[maxv]; stack<int>s;//存储拓扑排序，逆向输出为逆拓扑排序 bool topological(int n) { //拓扑排序，生成事件最早开始时间 fill(ve,ve+n+1,0);//从前向后推 queue<int>q; for(int i=1;i<=n;i++) if(indegree[i]==0) q.push(i); while(!q.empty()){ int t=q.front();q.pop(); s.push(t); for(int i=0;i<Adj[t].size();i++){ int x=Adj[t][i].v,w=Adj[t][i].w; indegree[x]--; if(indegree[x]==0) q.push(x); if(ve[t]+w>ve[x])//x位置的最早时间等于之前最长的路 ve[x]=ve[t]+w; } } if(s.size()==n)return true; return false; } int createvl(int n) {//生成事物的最迟开始时间 int maxlength=0; for(int i=1;i<=n;i++) //找到汇点 if(ve[i]>maxlength) maxlength=ve[i]; fill(vl,vl+n+1,maxlength);//从后往前推 while(!s.empty()){ int t=s.top() ;s.pop(); for(int i=0;i<Adj[t].size();i++) { int x=Adj[t][i].v; if(vl[x]-Adj[t][i].w<vl[t]) //t处最迟开始时间等于 之后路径最迟开始时间的最小值 vl[t]=vl[x]-Adj[t][i].w; } } return maxlength; } int criticalpath(int n) { if(topological(n)==false) return-1; int k=createvl(n); for(int i=1;i<=n;i++) for(int j=0;j<Adj[i].size();j++){ int x=Adj[i][j].v,w=Adj[i][j].w; int e=ve[i],l=vl[x]-w; if(e==l) printf("%d->%d\n",i,x); } return k; //返回路径和 } int main(){ int n,m,x,y,w; scanf("%d%d",&n,&m); node t; fill(indegree,indegree+n+1,0); for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&w); t.v=y;t.w=w; Adj[x].push_back(t); indegree[y]++; } criticalpath(n); return 0; }
