python 关键路径

关键路径是项目管理中的一个重要概念，用于确定项目中最长的路径和关键任务。在Python中，可以使用网络图和拓扑排序来计算关键路径。

以下是一个使用Python计算关键路径的示例：

import networkx as nx

# 创建有向无环图
G = nx.DiGraph()

# 添加任务节点
G.add_node('A', duration=3)
G.add_node('B', duration=2)
G.add_node('C', duration=4)
G.add_node('D', duration=5)
G.add_node('E', duration=2)
G.add_node('F', duration=3)
G.add_node('G', duration=4)

# 添加任务之间的依赖关系
G.add_edge('A', 'B')
G.add_edge('A', 'C')
G.add_edge('B', 'D')
G.add_edge('C', 'D')
G.add_edge('C', 'E')
G.add_edge('D', 'F')
G.add_edge('E', 'F')
G.add_edge('F', 'G')

# 计算关键路径
critical_path = nx.dag_longest_path(G)

# 输出关键路径
print("Critical Path:", critical_path)

运行以上代码，将输出关键路径：['A', 'C', 'E', 'F', 'G']。

相关问题

python关键路径算法

关键路径算法是一种用于确定项目中关键活动和关键路径的方法。在Python中，可以使用网络分析库NetworkX来实现关键路径算法。

下面是一个使用NetworkX库计算关键路径的示例代码：

import networkx as nx

# 创建有向图
G = nx.DiGraph()

# 添加活动节点
G.add_node('A', duration=5)
G.add_node('B', duration=3)
G.add_node('C', duration=2)
G.add_node('D', duration=4)
G.add_node('E', duration=6)
G.add_node('F', duration=2)
G.add_node('G', duration=4)
G.add_node('H', duration=1)

# 添加活动之间的依赖关系
G.add_edge('A', 'B')
G.add_edge('A', 'C')
G.add_edge('B', 'D')
G.add_edge('C', 'D')
G.add_edge('C', 'E')
G.add_edge('D', 'F')
G.add_edge('E', 'F')
G.add_edge('F', 'G')
G.add_edge('G', 'H')

# 计算关键路径
critical_path = nx.dag_longest_path(G)

# 输出关键路径
print("Critical Path:", critical_path)

运行以上代码，将输出关键路径。关键路径是指项目中最长的路径，它决定了项目的最短完成时间。

python关键路径怎么求

关键路径是项目中时间最长的活动顺序，决定着可能的项目最短工期。在Python中，可以使用拓扑排序和动态规划的方法来求解关键路径。

以下是一个使用Python实现关键路径的示例：

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices

    def addEdge(self, u, v, w):
        self.graph[u].append((v, w))

    def topologicalSortUtil(self, v, visited, stack):
        visited[v] = True

        if v in self.graph:
            for node, weight in self.graph[v]:
                if visited[node] == False:
                    self.topologicalSortUtil(node, visited, stack)

        stack.append(v)

    def topologicalSort(self):
        visited = [False] * self.V
        stack = []

 for i in range(self.V):
            if visited[i] == False:
                self.topologicalSortUtil(i, visited, stack)

        return stack[::-1]

    def longestPath(self, source):
        dist = [float("-inf")] * self.V
        dist[source] = 0

        topological_order = self.topologicalSort()

        for i in topological_order:
            if dist[i] != float("-inf"):
                for node, weight in self.graph[i]:
                    if dist[node] < dist[i] + weight:
                        dist[node] = dist[i] + weight

        return dist

# 创建一个有向加权图
g = Graph(6)
g.addEdge(0, 1, 5)
g.addEdge(0, 2, 3)
g.addEdge(1, 3, 6)
g.addEdge(1, 2, 2)
g.addEdge(2, 4, 4)
g.addEdge(2, 5, 2)
g.addEdge(2, 3, 7)
g.addEdge(3, 4, -1)
g.addEdge(4, 5, -2)

source = 1
dist = g.longestPath(source)

print("关键路径的长度为:")
for i in range(len(dist)):
    if dist[i] != float("-inf"):
        print(f"从节点 {source} 到节点 {i} 的最长路径长度为 {dist[i]}")

这段代码中，首先创建了一个有向加权图，并添加了边和权重。然后使用拓扑排序的方法获取节点的顺序。接着使用动态规划的方法计算每个节点的最长路径长度。最后输出关键路径的长度。