求關鍵路徑，只需理解頂點（事件）和邊（活動）各自的兩個特征屬性以及求法即可：
?? 先根據首結點的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 01 2 3 0 12 4 2 3 42 5 3 3 43 6 3 2 5* 3 4 4 2 2* 4 6 2 6 65 6 1 6 7*/criticalPathx();/*輸出結果：3 6 3 2 5* 4 6 2 6 6* 3 4 4 2 2* 1 3 2 0 02 4 2 3 45 6 1 6 72 5 3 3 41 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
? ?
用法)
)
)
