Python bellmanford代码实现
时间: 2023-11-05 13:30:50 浏览: 32
下面是 Python 代码实现 Bellman-Ford 算法:
```python
INF = 999999999
def bellman_ford(graph, start):
# 初始化距离数组
dist = [INF] * len(graph)
dist[start] = 0
# 进行 len(graph) - 1 轮松弛操作
for i in range(len(graph) - 1):
for u in range(len(graph)):
for v, w in graph[u]:
if dist[u] != INF and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# 检查是否存在负权回路
for u in range(len(graph)):
for v, w in graph[u]:
if dist[u] != INF and dist[u] + w < dist[v]:
return None
return dist
```
其中,`graph` 是一个邻接表形式的图表示,`start` 是起点的编号。在这个实现中,我们使用一个数组 `dist` 来记录每个点到起点的距离,初始化为一个大数,表示不可达。然后进行 `len(graph) - 1` 轮松弛操作,即对每条边进行更新,直到所有点的距离都被确定。最后再次遍历所有边,检查是否存在负权回路,如果存在,则算法返回 `None`,表示不存在最短路。如果不存在,则返回 `dist`,表示每个点到起点的最短距离。