Bellman-Ford算法实现

Bellman-Ford算法是一种用于解决单源最短路径问题的动态规划算法。以下是Bellman-Ford算法的实现：

1. 初始化距离数组dist[]，将源节点s的距离设置为0，其他节点的距离设置为无穷大。

2. 对于图中的每个节点，执行以下步骤：

a. 对于节点v的每个邻居节点u，如果dist[v] + weight(v, u) < dist[u]，则更新dist[u]为dist[v] + weight(v, u)。

3. 重复执行第2步，直到没有任何节点的距离值发生变化或执行了n-1次循环（n为节点数）。

4. 如果在第3步中仍然有节点的距离值发生变化，则说明存在负环路。

以下是Bellman-Ford算法的Python实现：

INF = float('inf')

def bellman_ford(graph, source):
    nodes = list(graph.keys())
    dist = {node: INF for node in nodes}
    dist[source] = 0
    for i in range(len(nodes) - 1):
        for u in nodes:
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
    for u in nodes:
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                return None # Negative cycle detected
    return dist

其中，graph是一个字典，键为节点，值为该节点的邻居节点及对应的边权重。例如，对于如下图：

      2
  (0)---(1)
   | \   |
 6 |  8\ | 7
   |   \ |
  (3)---(2)
      3

图的表示方式为：

graph = {
    0: [(1, 2), (3, 6)],
    1: [(0, 2), (2, 7)],
    2: [(1, 7), (3, 3)],
    3: [(0, 6), (2, 3)]
}

例如，调用bellman_ford(graph, 0)即可求出从节点0到其他节点的最短距离。如果存在负环路，则返回None。