python bellmanford代码实现
时间: 2023-07-23 17:42:34 浏览: 44
Bellman-Ford算法是一种单源最短路径算法,可以处理负权边。下面给出Python的实现代码:
```python
INF = float('inf')
def bellman_ford(graph, start):
"""
:param graph: 图,使用邻接表表示
:param start: 起点
:return: 起点到各个点的最短路径长度
"""
# 初始化距离数组
distance = {}
for node in graph:
distance[node] = INF
distance[start] = 0
# 进行n-1轮松弛操作
for i in range(len(graph)-1):
for u in graph:
for v, w in graph[u]:
if distance[u] != INF and distance[u] + w < distance[v]:
distance[v] = distance[u] + w
# 检查是否存在负权回路
for u in graph:
for v, w in graph[u]:
if distance[u] != INF and distance[u] + w < distance[v]:
raise ValueError("存在负权回路")
return distance
```
其中,`graph`是使用邻接表表示的图,`start`是起点。这个算法的时间复杂度是$O(|V| \times |E|)$,其中$|V|$和$|E|$分别是图的节点数和边数。