目录

一、关键路径

二、实现

三、小结

一、关键路径

关键路径AOE（Activity On Edge）算法是一种用于项目管理中确定项目最短完成时间和关键活动的算法，基于有向无环图（DAG）模型，AOE算法的核心思想是通过构建一个有向无环图（DAG）来表示项目中的活动和事件。

二、实现

package Algorithm.aoe
import std.collection.*

class Edge {
    // 目标顶点
    public var to: Int64
    // 活动持续时间
    public var duration: Int64

    public init(to: Int64, duration: Int64) {
        this.to = to
        this.duration = duration
    }
}

public class AOECriticalPath {
    public let MAX_VALUE = 99999999999
    private var vertices: Int64 // 顶点数
    private var adjList: ArrayList<ArrayList<Edge>> // 邻接表
    private var inDegree: Array<Int64> // 入度数组

    public init(vertices: Int64) {
        this.vertices = vertices
        this.adjList = ArrayList<ArrayList<Edge>>()
        this.inDegree = Array<Int64>(vertices, item: 0)
        for (_ in 0..vertices) {
            adjList.append(ArrayList<Edge>())
        }
    }

    // 添加边
    public func addEdge(from: Int64, to: Int64, duration: Int64): Unit {
        this.adjList[from].append(Edge(to, duration))
        this.inDegree[to]++
    }

    // 拓扑排序
    public func topologicalSort(): ArrayList<Int64> {
        let queue = ArrayList<Int64>()
        let topoOrder = ArrayList<Int64>()

        // 初始化队列，将所有入度为0的顶点加入队列
        for (i in 0..this.vertices) {
            if (inDegree[i] == 0) {
                queue.append(i)
            }
        }
        
        while (!queue.isEmpty()) {
            var u = queue.remove(0)
            topoOrder.append(u)

            for (edge in 0..this.adjList[u].size) {
                let v = this.adjList[u][edge].to
                this.inDegree[v]--
                if (inDegree[v] == 0) {
                    queue.append(v)
                }
            }
        }
        
        // 检查是否有环
        if (topoOrder.size != vertices) {
            println("图中存在环，无法进行拓扑排序")
        }
        
        return topoOrder
    }

    // 计算关键路径
    public func calculateCriticalPath(): Unit {
        // 1. 拓扑排序
        let topoOrder = topologicalSort()
        
        // 2. 初始化事件的最早发生时间(ET)和最晚发生时间(LT)
        let ET = Array<Int64>(this.vertices, item: -1)
        let LT = Array<Int64>(this.vertices, item: MAX_VALUE)
        
        LT[topoOrder[(topoOrder.size - 1)]] = ET[topoOrder[(topoOrder.size - 1)]]
        
        // 3. 计算ET（正向遍历拓扑序列）
        for (i in 0..topoOrder.size) {
            let u = topoOrder[i]
            for (edge in 0..this.adjList[u].size) {
                let v = this.adjList[u][edge].to
                if (ET[v] < ET[u] + this.adjList[u][edge].duration) {
                    ET[v] = ET[u] + this.adjList[u][edge].duration
                }
            }
        }
        
        // 4. 计算LT（逆向遍历拓扑序列）
        for (i in topoOrder.size - 1..=0:-1) {
            let u = topoOrder[i]
            for (edge in 0..this.adjList[u].size) {
                let v = this.adjList[u][edge].to
                if (LT[u] > LT[v] - this.adjList[u][edge].duration) {
                    LT[u] = LT[v] - this.adjList[u][edge].duration
                }
            }
        }
        
        // 5. 计算关键活动和关键路径
        println("关键路径长度: ${ET[topoOrder[(topoOrder.size - 1)]]}")
        println("关键路径:")
        
        // 构建逆向邻接表用于回溯关键路径
        let reverseAdj = HashMap<Int64, ArrayList<Edge>>()
        for (i in 0..this.vertices) {
            reverseAdj.put(i, ArrayList<Edge>())
        }
        
        for (u in 0..this.vertices) {
            for (edge in 0..this.adjList[u].size) {
                reverseAdj[this.adjList[u][edge].to].append(Edge(u, this.adjList[u][edge].duration))
            }
        }
        
        // 从汇点开始回溯关键路径
        var current = topoOrder[topoOrder.size - 1]
        var criticalPath = ArrayList<Int64>()
        criticalPath.append(current)
        
        while (current != topoOrder[0]) {
            for (edge in 0..reverseAdj[current].size) {
                let prev = reverseAdj[current][edge].to
                if (ET[prev] + reverseAdj[current][edge].duration == ET[current] && 
                    LT[prev] == LT[current] - reverseAdj[current][edge].duration) {
                    criticalPath.append(prev)
                    current = prev
                    break
                }
            }
        }
        criticalPath.reverse()
        println(criticalPath)
        
        // 输出所有关键活动
        println("关键活动:")
        for (u in 0..this.vertices) {
            for (edge in 0..this.adjList[u].size) {
                let v = this.adjList[u][edge].to
                if (ET[u] == LT[v] - this.adjList[u][edge].duration && ET[v] == ET[u] + this.adjList[u][edge].duration) {
                    println("活动 ${u} -> ${v} (持续时间: ${this.adjList[u][edge].duration})")
                }
            }
        }
    }
}

测试代码

package Algorithm
import Algorithm.aoe.*

main(): Int64 {
    // 示例：构建一个AOE网络
    let aoe = AOECriticalPath(6)
        
    // 添加边（活动）
    aoe.addEdge(0, 1, 3)
    aoe.addEdge(0, 2, 2)
    aoe.addEdge(1, 3, 4)
    aoe.addEdge(1, 4, 3)
    aoe.addEdge(2, 4, 2)
    aoe.addEdge(3, 5, 2)
    aoe.addEdge(4, 5, 4)
        
    // 计算并输出关键路径
    aoe.calculateCriticalPath()
    return 0
}

三、小结

本章为大家详细的介绍了仓颉数据结构与算法中关键路径的内容，下一章，为大家带来BF算法的内容。最后，创作不易，如果大家觉得我的文章对学习仓颉数据结构与算法有帮助的话，就动动小手，点个免费的赞吧！收到的赞越多，我的创作动力也会越大哦，谢谢大家🌹🌹🌹！！！