Bellman-Ford算法具体代码实现

Bellman-Ford算法是一种单源最短路径算法，它可以处理负权边，但不能处理负权环。下面是Bellman-Ford算法的具体代码实现：

INF = float('inf')

def bellman_ford(graph, start):
    # 初始化距离数组
    dist = {node: INF for node in graph}
    dist[start] = 0
    
    # 进行V-1轮松弛操作
    for i in range(len(graph) - 1):
        for u in graph:
            for v, w in graph[u].items():
                if dist[u] != INF and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
    
    # 判断是否有负权环
    for u in graph:
        for v, w in graph[u].items():
            if dist[u] != INF and dist[u] + w < dist[v]:
                raise ValueError('Graph contains a negative-weight cycle')
    
    return dist

其中，`graph`是一个邻接表，表示图的结构和权重；`start`是起点的标识符。函数的返回值是一个字典，表示从起点到每个节点的最短距离。

该算法的时间复杂度是$O(|V|\cdot|E|)$，其中$|V|$是节点数，$|E|$是边数。