C語言實現AOE網關鍵路徑算法：項目調度核心技術

編輯：關於C語言

AOE網關鍵路徑C語言實現：從拓撲排序到關鍵活動識別

AOE網(Activity On Edge Network)是項目管理中用於關鍵路徑分析的有向無環圖模型。本文提供完整的C語言實現，涵蓋圖的鄰接表構建、拓撲排序求最早/最晚事件時間、關鍵活動識別及關鍵路徑輸出全流程。

AOE網核心概念

事件(頂點)：項目里程碑，如「設計完成」、「測試開始」
活動(邊)：耗時任務，如「編寫代碼(5天)」、「系統測試(3天)」
關鍵路徑：從源點到匯點最長路徑，決定項目最短工期
關鍵活動：關鍵路徑上的活動，任何延遲都會推遲整個項目

數據結構設計

void CreateGraph(AOEGraph *G, int vexNum, int arcNum) {
    // 初始化頂點
    for (int i = 0; i < vexNum; i++) {
        printf("輸入頂點%d標識: ", i);
        scanf(" %c", &G->vertices[i].data);
        G->vertices[i].firstEdge = NULL;
        G->vertices[i].id = 0;
    }
    
    // 輸入邊信息
    for (int k = 0; k < arcNum; k++) {
        int begin, end, duration;
        printf("輸入邊%d(起點 終點 持續時間): ", k);
        scanf("%d %d %d", &begin, &end, &duration);
        
        // 頂點編號從1開始，數組從0開始
        begin--; end--;
        
        // 頭插法構建鄰接表
        EdgeNode *e = malloc(sizeof(EdgeNode));
        e->adjvex = end;
        e->weight = duration;
        e->next = G->vertices[begin].firstEdge;
        G->vertices[begin].firstEdge = e;
        
        // 終點入度++
        G->vertices[end].id++;
    }
    G->vexNum = vexNum;
    G->arcNum = arcNum;
}

2. 拓撲排序 + 最早事件時間(ve)計算

void CalculateLatestTimes(AOEGraph *G, int *topoOrder, int *ve, int *vl) {
    // 初始化vl為汇點最早時間(項目總工期)
    for (int i = 0; i < G->vexNum; i++) {
        vl[i] = ve[G->vexNum - 1];
    }
    
    // 逆序處理拓撲序列
    for (int i = G->vexNum - 1; i >= 0; i--) {
        int u = topoOrder[i];
        EdgeNode *e = G->vertices[u].firstEdge;
        while (e) {
            int v = e->adjvex;
            // vl[u] = min(vl[u], vl[v] - weight)
            if (vl[v] - e->weight < vl[u]) {
                vl[u] = vl[v] - e->weight;
            }
            e = e->next;
        }
    }
}

4. 關鍵活動識別與關鍵路徑輸出

vexNum; i++) {
        int u = topoOrder[i];
        EdgeNode *e = G->vertices[u].firstEdge;
        while (e) {
            int v = e->adjvex;
            int ee = ve[u];           // 活動最早開始時間
            int el = vl[v] - e->weight; // 活動最晚開始時間
            int slack = el - ee;       // 浮動時間
            
            printf("| %c->%c | %4c | %4c | %8d | %8d | %6d | %s |\n",
                   G->vertices[u].data, G->vertices[v].data,
                   G->vertices[u].data, G->vertices[v].data,
                   ee, el, slack, slack == 0 ? "是" : "否");
            
            // 關鍵活動浮動時間為0
            if (slack == 0) {
                criticalPath[cpLen++] = G->vertices[u].data;
            }
            e = e->next;
        }
    }
    
    // 輸出關鍵路徑(去重+添加匯點)
    printf("\n關鍵路徑: ");
    for (int i = 0; i < cpLen; i++) {
        if (i == 0 || criticalPath[i] != criticalPath[i-1]) {
            printf("%c -> ", criticalPath[i]);
        }
    }
    printf("%c\n", G->vertices[G->vexNum-1].data);
    printf("項目總工期: %d 時間單位\n", ve[G->vexNum-1]);
}

完整主程序與測試




測試數據示例
頂點: 6, 邊: 8
頂點標識: A B C D E F
邊:
1 2 3  (A->B, 3)
1 3 4  (A->C, 4)
2 4 5  (B->D, 5)
3 4 4  (C->D, 4)
2 5 6  (B->E, 6)
3 5 5  (C->E, 5)
4 6 2  (D->F, 2)
5 6 3  (E->F, 3)


輸出結果解析
| 活動 | 起點 | 終點 | 最早開始 | 最晚開始 | 浮動時間 | 關鍵 |
| A->B |    A |    B |        0 |        0 |      0 | 是  |
| A->C |    A |    C |        0 |        1 |      1 | 否  |
| B->D |    B |    D |        3 |        3 |      0 | 是  |
| C->D |    C |    D |        4 |        4 |      0 | 是  |
| B->E |    B |    E |        3 |        4 |      1 | 否  |
| C->E |    C |    E |        4 |        5 |      1 | 否  |
| D->F |    D |    F |        8 |        8 |      0 | 是  |
| E->F |    E |    F |        9 |        9 |      0 | 是  |

關鍵路徑: A -> B -> D -> F
項目總工期: 10 時間單位


關鍵路徑算法複雜度

階段 時間複雜度 空間複雜度
拓撲排序+ve O(V+E) O(V)
逆序計算vl O(V+E) O(V)
關鍵活動識別 O(E) O(1)
總計 O(V+E) O(V)


工程應用與擴展

並行項目調度：非關鍵活動浮動時間內可靈活安排資源
資源平衡：根據浮動時間優化資源分配
風險管理：關鍵活動需重點監控與風險預案
進度壓縮：僅壓縮關鍵路徑活動才能縮短總工期


AOE網關鍵路徑算法是運籌學與項目管理的基石，C語言實現通過鄰接表+拓撲排序+動態規劃思想，高效解決了項目最短工期與關鍵活動識別問題。掌握其核心邏輯，對理解編譯器指令調度、CI/CD流水線優化、雲資源調度等現代工程問題大有裨益。