golang实现关键路径算法

关键路径算法（Critical Path Method，简称CPM）是一种用于项目管理的技术，主要用于计算项目中的关键路径和关键活动。关键路径是指项目中的最长路径，决定了项目的最短完成时间。关键活动是指在关键路径上的活动，必须按时完成才能确保项目按计划完成。

关键路径算法通常包含如下步骤：一是确定项目的所有活动和它们之间的先后关系，建立活动网络图。需要注意的是活动网络图必须是有向无环图。二是计算每个活动的最早开始时间和最晚结束时间。三是根据活动的持续时间和先后关系，计算活动的总浮动时间和自由浮动时间。四是根据活动的最早开始时间和最迟开始时间，确定关键路径和关键活动，计算项目的总时间。

以下是用go语言实现的关键路径算法：

首先定义任务结构体：

type Task struct {id             string  // 任务IDduration       int     // 任务持续时间dependencies   []*Task // 前置任务列表successors     []*Task // 后继任务列表earliestStart  int     // 最早开始时间latestStart    int     // 最晚开始时间
}

其次是对当前任务序列进行拓扑排序，并检查是否是有向无环图。

func topologicalSort(tasks []*Task) ([]*Task,bool) {n := len(tasks)visited := make(map[*Task]int)  //记录每个任务的访问状态，0表示没有访问过，1表示已经访问过了，2表示访问完成order := make([]*Task,n) //排序结果
​index := n - 1cycle := falsevar dfs func(node *Task) //遍历函数dfs = func(node *Task) {visited[node] = 1for _, neighbor := range node.successors {if visited[neighbor] == 0 {dfs(neighbor)} else if visited[neighbor] == 1 {cycle = truereturn}}visited[node] = 2order[index] = nodeindex--}
​for _,task := range tasks {if visited[task] == 0 {dfs(task)if cycle {return nil, false}}}
​return order, true
}

排序函数将一组活动列表作为参数传入，然后递归遍历所有活动结点，将排序结果作为第一个返回值返回，第二个返回值为布尔类型，true表示是有向无环图，false表示当前活动网络图有环。

然后计算每个活动的最早开始时间和最晚开始时间：

func (s *Schedule)calculateEarlyStart(task *Task) int {// -1为默认值，如果最早开始时间不为-1表示已经设置过最早开始时间了if task.earliestStart != -1 {return task.earliestStart}maxEarlyStart := 0//计算所有前置任务的最晚结束时间for _, predecessor := range task.dependencies {earlyStart := s.calculateEarlyStart(predecessor) + predecessor.durationif earlyStart > maxEarlyStart {maxEarlyStart = earlyStart}}//前置任务的的最晚结束时间即当前活动的最早开始时间task.earliestStart = maxEarlyStartreturn maxEarlyStart
}
​
func (s *Schedule)calculateLateStart(task *Task,projectDuration int) int {if task.latestStart != -1 {return task.latestStart}//如果当前活动没有后置任务，当前任务的最晚开始时间设置为项目结束时间减去当前任务的持续时间if len(task.successors) == 0 {task.latestStart = projectDuration - task.durationreturn task.latestStart}//计算后置任务的最早开始时间minLateStart := projectDurationfor _,successor := range task.successors {lateStart := s.calculateLateStart(successor, projectDuration) - task.durationif lateStart < minLateStart {minLateStart = lateStart}}task.latestStart = minLateStartreturn minLateStart
}

计算完每个任务的最早开始时间和最晚开始减后，根据关键活动的定义找出关键路径。

func (s *Schedule)CriticalPath() ([]*Task,int) {criticalPath := make([]*Task,0)projectDuration := 0// 计算任务的最早开始时间,确定项目的最早结束时间for _,task := range s.tasks {task.earliestStart = -1task.latestStart = -1earlyStart := s.calculateEarlyStart(task)if earlyStart + task.duration > projectDuration {projectDuration = earlyStart + task.duration}}// 计算任务的最晚开始时间，如果任务的最早开始时间等于最晚开始时间则为关键活动for _,task := range s.tasks {s.calculateLateStart(task, projectDuration)if task.earliestStart == task.latestStart {criticalPath = append(criticalPath, task)}}return criticalPath,projectDuration
}

以上就是用golang实现的关键路径算法，Schedule是项目排期结构体，由项目的活动序列组成。关键路径算法可以帮助项目管理者合理安排项目计划和资源分配，以确保项目按计划完成，并能及时发现和解决可能导致项目延误的问题。它被广泛应用于建筑、制造、软件开发等众多行业中。