求关键路径，只需理解顶点（事件）和边（活动）各自的两个特征属性以及求法即可：
Ø 先根据首结点的Ve(j)=0由前向后（正拓扑序列）计算各顶点的最早发生时间
Ø 再根据终结点的Vl(j)等于它的Ve(j)由后向前（逆序拓扑）依次求解各顶点的最晚发生时间
Ø 根据边的ee(i)等于它的发出顶点的Ve(j)计算各边的最早开始时间（最早开始，对应最早发生）
Ø 根据边的ll(i)等于它的到达顶点的Vl(j)减去边的权值计算各边的最晚开始时间（最晚开始，对应最晚发生）
#include<iostream>
#include<cstring> #include<cstdio> #include<cstdlib> #include<vector> #include<stack> #define MAX_NODE_NUM 100 using namespace std; int first[MAX_NODE_NUM]; typedef struct EDGE{ int u, v, w; int nextarc; EDGE(){ } EDGE(int u, int v, int w, int nextarc){ this->u = u; this->v = v; this->w = w; this->nextarc = nextarc; } } edge; vector<edge> g; stack<int> s, t;//s存储入度为零的节点， t存储图的拓扑序列的顶点栈 int ve[MAX_NODE_NUM];//事件的最早发生时间， 或者 活动ai的最早发生时间 int vl[MAX_NODE_NUM];//事件的最晚发生时间 int degIn[MAX_NODE_NUM];//记录每一个节点的入度 int tag[MAX_NODE_NUM][MAX_NODE_NUM]; int n, m;//分别为图的节点的个数，和边的个数 bool topoSort(){ memset(ve, 0, sizeof(ve)); int cnt = 0;//记录 for(int i=1; i<=n; ++i) if(degIn[i] == 0) s.push(i); while(!s.empty()){ int u = s.top(); s.pop(); t.push(u); ++cnt; for(int e=first[u]; ~e; e=g[e].nextarc){ int v = g[e].v; int w = g[e].w; if(--degIn[v] == 0) s.push(v); if(ve[u] + w > ve[v]) ve[v] = ve[u] + w; } } if(cnt < n) return false;//该有向图存在回路 return true; } bool criticalPath() {//寻找关键路径 if(!topoSort()) return false; for(int i=1; i<=n; ++i) vl[i] = ve[t.top()]; while(!t.empty()){//逆序拓扑排序，计算每个节点的最晚的发生时间 int u = t.top(); t.pop(); for(int e=first[u]; ~e; e=g[e].nextarc){ int v = g[e].v; int w = g[e].w; if(vl[v] - w < vl[u]) vl[u] = vl[v] - w; } } for(int i=1; i<=n; ++i){//输出关节点 int ee = ve[i];//活动ai的最早的发生时间 for(int e=first[i]; ~e; e=g[e].nextarc) { int v = g[e].v; int w = g[e].w; int ll = vl[v]-w;//活动ai的最晚的发生时间 ll == ee ? printf(" * ") : printf(" "); printf("%d %d %d %d %d\n", i, v, w, ee, ll);//分别为 u, v, w(这条边所对应的活动)， 活动最早发生时间和最晚发生时间 } } return true; } void dfs(int u){ for(int e=first[u]; ~e; e=g[e].nextarc) { int ee = ve[u]; int v = g[e].v; int w = g[e].w; dfs(v); if(tag[u][v]) continue; tag[u][v] = 1; if(vl[v]-w < vl[u]) vl[u] = vl[v]-w; int ll = vl[v]-w;//活动au的最晚的发生时间 ll == ee ? printf(" * ") : printf(" "); printf("%d %d %d %d %d\n", u, v, w, ee, ll); } } bool criticalPathx() {//寻找关键路径,利用dfs可以 if(!topoSort()) return false; for(int i=1; i<=n; ++i) vl[i] = ve[t.top()]; dfs(1);//默认1节点为源点 } void addEdge(int u, int v, int w){ edge e(u, v, w, first[u]); first[u] = g.size(); g.push_back(e); } int main(){ printf("请输入图的节点的个数和边的个数:\n"); scanf("%d%d", &n, &m); memset(first, -1, sizeof(first)); while(m--){ int u, v, w; scanf("%d %d %d", &u, &v, &w); addEdge(u, v, w); ++degIn[v]; } //criticalPath(); /*输出结果： * 1 3 2 0 0 1 2 3 0 1 2 4 2 3 4 2 5 3 3 4 3 6 3 2 5 * 3 4 4 2 2 * 4 6 2 6 6 5 6 1 6 7 */ criticalPathx(); /*输出结果： 3 6 3 2 5 * 4 6 2 6 6 * 3 4 4 2 2 * 1 3 2 0 0 2 4 2 3 4 5 6 1 6 7 2 5 3 3 4 1 2 3 0 1 */ return 0; }
输入数据：
6 8
1 2 3
2 5 3
5 6 1
2 4 2
4 6 2
3 4 4
1 3 2
3 6 3
