数据结构 实验关键路径

关键路径是指在一个项目中，所有活动中最长的路径，它决定了整个项目的完成期限。关键路径分析是一种用来确定关键任务和关键路径的管理工具。下面是实现关键路径的步骤：

1. 读取数据，建立AOE网络邻接表存储结构。
2. 对AOE网络进行拓扑排序，得到每个顶点的最早开始时间。
3. 对AOE网络进行逆拓扑排序，得到每个顶点的最晚开始时间。
4. 计算每个活动的最早开始时间和最晚开始时间。
5. 计算每个活动的总时差。
6. 找到所有总时差为0的活动，这些活动组成了关键路径。
7. 输出关键路径和工程的最短完成时间。

下面是Python代码实现：

class Vertex:
    def __init__(self, name):
        self.name = name
        self.in_degree = 0
        self.out_degree = 0
        self.early_start = 0
        self.late_start = float('inf')
        self.adjacent = {}

    def add_neighbor(self, neighbor, weight=0):
        self.adjacent[neighbor] = weight
        neighbor.in_degree += 1
        self.out_degree += 1


class Graph:
    def __init__(self):
        self.vertices = {}

    def add_vertex(self, vertex):
        self.vertices[vertex.name] = vertex

    def get_vertex(self, name):
        if name not in self.vertices:
            self.vertices[name] = Vertex(name)
        return self.vertices[name]

    def add_edge(self, frm, to, weight=0):
        if frm not in self.vertices:
            self.add_vertex(Vertex(frm))
        if to not in self.vertices:
            self.add_vertex(Vertex(to))
        self.vertices[frm].add_neighbor(self.vertices[to], weight)

    def topsort(self):
        queue = []
        for vertex in self.vertices.values():
            if vertex.in_degree == 0:
                queue.append(vertex)

        while queue:
            current_vertex = queue.pop(0)
            print(current_vertex.name)
            for neighbor in current_vertex.adjacent:
                neighbor.in_degree -= 1
                if neighbor.in_degree == 0:
                    queue.append(neighbor)

    def critical_path(self):
        for vertex in self.vertices.values():
            if vertex.in_degree == 0:
                vertex.early_start = 0

        stack = []
        for vertex in self.vertices.values():
            if vertex.in_degree == 0:
                stack.append(vertex)

        while stack:
            current_vertex = stack.pop()
            for neighbor in current_vertex.adjacent:
                if neighbor.early_start < current_vertex.early_start + current_vertex.adjacent[neighbor]:
                    neighbor.early_start = current_vertex.early_start + current_vertex.adjacent[neighbor]
            stack.extend([neighbor for neighbor in current_vertex.adjacent if neighbor.in_degree > 0])
        
        for vertex in self.vertices.values():
            if vertex.out_degree == 0:
                vertex.late_start = vertex.early_start

        stack = []
        for vertex in self.vertices.values():
            if vertex.out_degree == 0:
                stack.append(vertex)

        while stack:
            current_vertex = stack.pop()
            for neighbor in self.vertices.values():
                if current_vertex in neighbor.adjacent:
                    if neighbor.late_start > current_vertex.late_start - neighbor.adjacent[current_vertex]:
                        neighbor.late_start = current_vertex.late_start - neighbor.adjacent[current_vertex]
            stack.extend([vertex for vertex in self.vertices.values() if vertex.out_degree > 0 and vertex.late_start < float('inf')])

        for vertex in self.vertices.values():
            for neighbor in vertex.adjacent:
                slack = neighbor.late_start - vertex.early_start - vertex.adjacent[neighbor]
                if slack == 0:
                    print(f'{vertex.name} -> {neighbor.name} is on the critical path')

        print(f'The shortest completion time is {max([vertex.early_start for vertex in self.vertices.values()])}')

# 读取数据，建立AOE网络邻接表存储结构
g = Graph()
g.add_edge('A', 'B', 3)
g.add_edge('A', 'C', 2)
g.add_edge('B', 'D', 5)
g.add_edge('C', 'D', 4)
g.add_edge('B', 'E', 6)
g.add_edge('D', 'F', 7)
g.add_edge('E', 'F', 8)

# 输出关键路径和工程的最短完成时间
g.critical_path()