python关键路径怎么求
时间: 2024-01-10 07:20:31 浏览: 30
关键路径是项目中时间最长的活动顺序,决定着可能的项目最短工期。在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]}")
```
这段代码中,首先创建了一个有向加权图,并添加了边和权重。然后使用拓扑排序的方法获取节点的顺序。接着使用动态规划的方法计算每个节点的最长路径长度。最后输出关键路径的长度。