關鍵路徑法 (CPM) Java 實現：專案排程核心演算法完整代碼

關鍵路徑法 (Critical Path Method, CPM) 用於專案管理中計算最早/最晚開始時間、浮動時間，識別決定專案工期的關鍵活動。本文提供基於鄰接表的 Java 實現，輸出所有關鍵路徑邊的並集。

資料結構定義

圖以二維陣列 int[][] graph 表示鄰接表：

• graph[v][0]：頂點 v 的出度（邊數）。
• graph[v][2*i-1]：第 i 條邊的目標頂點。
• graph[v][2*i]：第 i 條邊的權重（持續時間）。

核心演算法步驟

1. 拓撲排序：用堆疊實現 Kahn 演算法，獲得拓撲序列。
2. 前向遞推 (ve)：按拓撲序計算每個事件最早發生時間 ve[j] = max(ve[v] + w)。
3. 後向遞推 (vl)：逆拓撲序計算最晚發生時間 vl[v] = min(vl[j] - w)，終點 vl = ve。
4. 關鍵邊判定：邊 (v, j) 滿足 ve[v] == vl[j] - w 即為關鍵活動。

完整 Java 代碼

import java.util.Stack;

public class CriticalPath {
    private int[][] graph;
    private int[][] path;
    private int len;

    public void input(int[][] graph) {
        this.graph = graph;
        path = new int[graph.length - 1][3];
        calculate();
    }

    private void calculate() {
        int n = graph.length;
        int[] ve = new int[n];
        Stack st1 = new Stack<>(), st2 = new Stack<>();

        // 拓撲排序 + 前向遞推
        st1.push(0);
        while (!st1.isEmpty()) {
            int v = st1.pop();
            for (int i = 1; i < graph[v].length; i += 2) {
                int j = graph[v][i];
                if (--graph[j][0] == 0) st1.push(j);
                if (ve[v] + graph[v][i+1] > ve[j])
                    ve[j] = ve[v] + graph[v][i+1];
            }
            st2.push(v);
        }

        // 後向遞推
        int[] vl = new int[n];
        for (int i = 0; i < n; i++) vl[i] = Integer.MAX_VALUE;
        vl[n-1] = ve[n-1];
        while (!st2.isEmpty()) {
            int v = st2.pop();
            for (int i = 1; i < graph[v].length; i += 2) {
                int j = graph[v][i];
                if (vl[j] - graph[v][i+1] < vl[v])
                    vl[v] = vl[j] - graph[v][i+1];
            }
        }

        // 關鍵邊收集
        for (int v = 0; v < n-1; v++) {
            for (int i = 1; i < graph[v].length; i += 2) {
                int j = graph[v][i];
                int w = graph[v][i+1];
                if (ve[v] == vl[j] - w) {
                    path[len++] = new int[]{v, j, w};
                }
            }
        }
    }

    public int[][] getPath() { return path; }
    public int getLength() { return len; }
}

測試案例與輸出

int[][] graph = {
    {0, 1,6, 2,4, 3,5},   // 0→1(6) 0→2(4) 0→3(5)
    {1, 4,1},             // 1→4(1)
    {1, 4,1},             // 2→4(1)
    {1, 5,2},             // 3→5(2)
    {2, 6,9, 7,7},        // 4→6(9) 4→7(7)
    {1, 7,4},             // 5→7(4)
    {1, 8,2},             // 6→8(2)
    {2, 8,4},             // 7→8(4)
    {2}                   // 8 終點
};
// 輸出關鍵邊：
// 邊：0-1 權：6
// 邊：1-4 權：1
// 邊：4-6 權：9
// 邊：4-7 權：7
// 邊：6-8 權：2
// 邊：7-8 權：4
// 關鍵路徑：0-1-4-6-8 及 0-1-4-7-8

工程應用提示

• 輸入圖**必須為 DAG**（有向無環圖），否則拓撲排序失敗。
• 實際專案中活動節點數可能達萬級，建議改用 List 鄰接表降低空間複雜度。
• 浮動時間 float = vl[j] - ve[v] - w 可進一步識別非關鍵活動的緩衝空間。