关键路径AOE网络代码
时间: 2023-09-21 15:02:56 浏览: 56
以下是一个简单的 Python 代码示例,用于计算关键路径和 AOE 网络。
```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.keys():
for node, weight in self.graph[v]:
if visited[node] == False:
self.topologicalSortUtil(node, visited, stack)
stack.append(v)
def longestPath(self, s):
visited = {v: False for v in range(self.V)}
stack = []
for i in range(self.V):
if visited[i] == False:
self.topologicalSortUtil(s, visited, stack)
dist = {v: float('-inf') for v in range(self.V)}
dist[s] = 0
while stack:
i = stack.pop()
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
def criticalPath(self):
dist = self.longestPath(0)
critical_path = []
for i in range(self.V):
for node, weight in self.graph[i]:
if dist[i] != float('-inf') and dist[node] == dist[i] + weight:
critical_path.append((i, node, weight))
return critical_path
# 测试用例
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, 5, 1)
g.addEdge(3, 4, -1)
g.addEdge(4, 5, -2)
print("关键路径为:", g.criticalPath())
```
以上代码包括以下实现:
- 使用 `defaultdict` 创建一个有向图
- 添加边的方法 `addEdge`
- 实现拓扑排序的工具函数 `topologicalSortUtil`
- 计算最长路径的方法 `longestPath`
- 计算关键路径的方法 `criticalPath`
在本例中,我们使用了一个简单的测试用例。你可以根据自己的需求更改节点和边的数量、权重等参数。