引言很多同學學完拓撲排序只會用它給活動排個先后次序。但工程里真正被追問的是另一件事整個項目最早什么時候能干完哪些活兒一天都拖不得前者是“最長路”后者是“關鍵路徑Critical Path”。拓撲排序解決的是“能不能排”、解決“依賴是否合法”關鍵路徑在它之上再疊一層帶權最長路的推導是信奧提高組圖論里非常經(jīng)典、也極易踩坑的一個綜合考點。本文用一個校園科技節(jié)籌備排期的原創(chuàng)題把概念、推導、雙語言實現(xiàn)、易錯點和進階一次講透。一、題目與項目目標原創(chuàng)題校園科技節(jié)籌備排期學校要籌備科技節(jié)把所有籌備工作拆成了若干個“事件里程碑”。規(guī)定一共有n個事件編號1..n。事件1是“項目開工”事件n是“項目竣工”。有m條籌備活動用有向邊u → v表示權重w是該活動的工期天數(shù)w ≥ 0。含義是事件u完成之后活動u→v才能開工開工后需要w天。只要前置事件已全部完成多個活動可以并行推進。求兩件事整個科技節(jié)籌備的最早完成天數(shù)哪些活動是關鍵活動——它只要晚開工 1 天整個項目就會晚 1 天即“松弛時間為 0”的活動。這就是經(jīng)典的AOE 網(wǎng)Activity On Edge邊表示活動關鍵路徑問題。二、核心考點拓撲排序 判環(huán)有向圖若出現(xiàn)環(huán)說明依賴自相矛盾根本排不了期必須先檢測。事件最早發(fā)生時間ve在拓撲序上正向遞推本質是求“帶權 DAG 最長路”。事件最遲發(fā)生時間vl在逆拓撲序上反向遞推用min松弛。關鍵活動判定對邊u→v工期w最早開工e ve[u]最遲開工l vl[v] ? w當e l松弛時間 0時該活動關鍵。多匯點處理用“超級匯點”把多個出度為 0 的節(jié)點統(tǒng)一收口否則vl會被全局最長時間撐大、誤判關鍵活動。關鍵路徑還原順著關鍵活動把所有關鍵路徑走出來關鍵路徑可能不止一條。三、解法與拆解3.1 拓撲排序 判環(huán)用 Kahn 算法統(tǒng)計入度入度為 0 的入隊每次彈出并消減后繼入度。若最終排進拓撲序列的節(jié)點數(shù)不等于總節(jié)點數(shù)說明有環(huán)直接返回“無關鍵路徑”。3.2 正向求 ve最早發(fā)生時間 最長路初始化所有ve 0。按拓撲序遍歷每個節(jié)點u用它的每條出邊u→v權 w去松弛ve[v] max(ve[v], ve[u] w)因為拓撲序保證u一定在v之前被處理完等u的所有前驅都松弛過之后ve[u]已經(jīng)是“從開工到u的最長耗時”于是ve[v]自然收斂為“到v的最長耗時”。整個項目的最早完成時間T max(ve)也就是所有“終點事件”里最晚的那個。為了把多個終點統(tǒng)一成一個我們引入超級匯點n1把所有“出度為 0”的節(jié)點連一條權重 0 的邊到n1。這樣ve[n1]就等于全局最早完成時間T后面求vl也不用特殊判斷了。3.3 反向求 vl最遲發(fā)生時間初始化所有vl T。按逆拓撲序遍歷每個節(jié)點u用它的每條出邊u→v權 w去松弛vl[u] min(vl[u], vl[v] ? w)含義事件u最遲必須在vl[v] ? w之前發(fā)生才不耽誤后繼v的最遲發(fā)生。vl從終點往回推所以必須逆拓撲序。3.4 關鍵活動判定與路徑還原對每條原邊u→v權 w該活動最早開工e ve[u]該活動最遲開工l vl[v] ? w若e l說明它沒有一點緩沖是關鍵活動否則它的松弛時間就是l ? e。把所有關鍵活動收集起來從“開工且ve 0”的起點順著關鍵邊走就能還原出一條或多條關鍵路徑。四、時間 / 空間復雜度時間復雜度拓撲排序O(n m)正向ve與反向vl各掃一遍所有邊O(n m)合計O(n m)?？臻g復雜度鄰接表、入度、拓撲序、ve、vl各O(n m)邊主導即O(n m)。注意ve、vl用long long工期累加可能很大權值非負最長路有定義。五、易錯點重點有環(huán)不判直接遞推會死循環(huán)或結果錯誤必須先拓撲排序并校驗節(jié)點數(shù)有環(huán)則本題無解。多匯點必須接超級匯點若不處理多個“出度為 0”的終點它們的vl會被初始化成全局T而偏大從而把本不關鍵的活動誤判為關鍵。接一個權重 0 的超級匯點最穩(wěn)妥。ve 是取max最長路不是min求“最早完成”本質是 DAG 最長路和最短路的min正好相反別寫反。vl 必須逆拓撲序 取min順序錯了vl[v]還沒定下來就去松弛vl[u]結果必然錯。關鍵活動判定用ve[u] vl[v] ? w不是ve[u] vl[u]活動在邊上、工期在點之間混淆節(jié)點時間和邊時間是最常見的筆誤。關鍵路徑可能不止一條還原時要把所有滿足e l的邊都收集不能找到一條就停。工期必須非負出現(xiàn)負權時“最長路”無定義會變成求環(huán)NP-hard建圖時就要保證w ≥ 0。六、進階AOE 與 AOV 的區(qū)別本文是 AOE邊活動權工期AOV 是“點活動、邊先后約束、點不帶權”AOV 通常只做拓撲排序不談關鍵路徑。輸出所有關鍵路徑在關鍵活動子圖上做 DFS把每條從起點到終點的關鍵路徑都打印出來。與資源約束結合PERT / 項目調度若同一時刻能干活的人數(shù)有限關鍵路徑只是“理想并行下界”真實工期還要受資源限制那是更復雜的 RCPSP 問題一般 NP-hard。練習推薦洛谷P1113 雜務是關鍵路徑裸題P1238等可作鞏固。把本文代碼稍作改造即可直接套。與最短路對照記憶最短路d[v] min(d[v], d[u] w)正向、關鍵路徑ve[v] max(...)正向、vl反向min三者放在一起對比考試時不暈。七、小結與互動拓撲排序負責“能不能排”關鍵路徑負責“排完要多久、哪里不能拖”。掌握ve / vl / el三步再記住超級匯點和逆序求 vl兩個坑這道題在提高組里就是送分題。你刷題時還遇到過哪些“拓撲排序之后還能再進階”的題型歡迎在評論區(qū)聊聊下一篇我們可以寫“差分約束與關鍵路徑的親戚關系”。參考代碼C 實現(xiàn)#include bits/stdc.h using namespace std; // 返回 (T, 關鍵活動列表)有環(huán)則 T -1 pairlong long, vectortupleint, int, long long criticalPath( int n, const vectortupleint, int, long long edges) { vectorvectorpairint, long long g(n 2); // 1..n 超級匯點 n1 vectorint indeg(n 2, 0); for (auto e : edges) { int u get0(e), v get1(e); long long w get2(e); g[u].push_back({v, w}); indeg[v]; } // 超級匯點把出度為 0 的節(jié)點都連到 n1權 0統(tǒng)一成單匯點 for (int i 1; i n; i) if (g[i].empty()) { g[i].push_back({n 1, 0}); indeg[n 1]; } // Kahn 拓撲排序 queueint q; for (int i 1; i n 1; i) if (indeg[i] 0) q.push(i); vectorint topo; vectorint deg indeg; while (!q.empty()) { int u q.front(); q.pop(); topo.push_back(u); for (auto pr : g[u]) if (--deg[pr.first] 0) q.push(pr.first); } if ((int)topo.size() ! n 1) return {-1, {}}; // 有環(huán) vectorlong long ve(n 2, 0); for (int u : topo) for (auto pr : g[u]) ve[pr.first] max(ve[pr.first], ve[u] pr.second); long long T ve[n 1]; // 全局最早完成 vectorlong long vl(n 2, T); for (auto it topo.rbegin(); it ! topo.rend(); it) { int u *it; for (auto pr : g[u]) vl[u] min(vl[u], vl[pr.first] - pr.second); } vectortupleint, int, long long critical; for (auto e : edges) { int u get0(e), v get1(e); long long w get2(e); if (ve[u] vl[v] - w) critical.push_back(e); // 松弛時間 0 } return {T, critical}; }Python 實現(xiàn)from collections import deque def critical_path(n, edges): n: 事件數(shù) (1..n) edges: list of (u, v, w) 返回 (T, 關鍵活動列表)有環(huán)返回 (None, None) g [[] for _ in range(n 2)] # 1..n 超級匯點 n1 indeg [0] * (n 2) for u, v, w in edges: g[u].append((v, w)) indeg[v] 1 for i in range(1, n 1): # 出度為 0 的連到超級匯點 if not g[i]: g[i].append((n 1, 0)) indeg[n 1] 1 # Kahn 拓撲排序 deg indeg[:] q deque([i for i in range(1, n 2) if deg[i] 0]) topo [] while q: u q.popleft(); topo.append(u) for v, w in g[u]: deg[v] - 1 if deg[v] 0: q.append(v) if len(topo) ! n 1: return None, None # 有環(huán) ve [0] * (n 2) for u in topo: for v, w in g[u]: ve[v] max(ve[v], ve[u] w) T ve[n 1] vl [T] * (n 2) for u in reversed(topo): for v, w in g[u]: vl[u] min(vl[u], vl[v] - w) critical [(u, v, w) for u, v, w in edges if ve[u] vl[v] - w] return T, critical樣例演示輸入n6邊u v w1 2 3 1 4 4 2 3 2 2 5 3 3 6 5 4 3 1 4 5 1 5 6 4推導結果各事件最早發(fā)生ve事件10事件23事件44事件35事件56事件610最早完成T 10天。各事件最遲發(fā)生vl事件610事件56事件35事件44事件23事件10。關鍵活動松弛時間 01→2、1→4、2→3、2→5、3→6、4→3、5→6。非關鍵活動4→5其最早開工4、最遲開工5有 1 天松弛可晚 1 天開工不影響整體。關鍵路徑長度均為 101→2→3→6、1→2→5→6、1→4→3→6?？梢娂词?→5這條活動晚一天項目仍能按時完成而其它任何一條關鍵活動晚一天整體就晚一天。這正是關鍵路徑想告訴項目經(jīng)理的事。 免費少兒編程資料夸克網(wǎng)盤領取以下資料來自夸克網(wǎng)盤分享點擊鏈接可直接保存若需在 App 內打開也可復制下方明文鏈接全國青少年信息素養(yǎng)大賽復賽集訓題目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素養(yǎng)-智能算法應用挑戰(zhàn)賽-復賽初中組題目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背記手冊.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython課程https://pan.quark.cn/s/a94bf02d00c62024信息素養(yǎng)大賽圖形化復賽集訓題答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份電子學會考級真題https://pan.quark.cn/s/4403c42289122025全國青少年信息素養(yǎng)大賽賽項說明https://pan.quark.cn/s/d9d0df4a9f29青少兒信息素養(yǎng)大賽編程資料https://pan.quark.cn/s/4ab6bd83be8a資料持續(xù)更新關注獲取最新分享。