SPFA算法python实现

SPFA算法是一种基于Bellman-Ford算法的单源最短路径算法，它可以处理负权边，但是会因为负环而陷入无限循环。下面是SPFA算法的Python实现：

import collections

def spfa(graph, start):
    """
    :param graph: 图的邻接表表示， graph[u]表示与顶点u相连的边和权重
    :param start: 起点
    :return: 从起点到其他顶点的最短距离
    """
    # 初始化距离
    distance = {vertex: float('inf') for vertex in graph}
    distance[start] = 0

    # 初始化队列
    queue = collections.deque([start])

    # 记录每个顶点的入队次数，防止出现负环
    visit_count = {vertex: 0 for vertex in graph}
    visit_count[start] = 1

    # SPFA算法
    while queue:
        vertex = queue.popleft()
        for neighbor, weight in graph[vertex]:
            new_distance = distance[vertex] + weight
            if new_distance < distance[neighbor]:
                distance[neighbor] = new_distance
                visit_count[neighbor] += 1
                if visit_count[neighbor] > len(graph):
                    raise ValueError("图中存在负环")
                queue.append(neighbor)

    return distance

该算法使用了Python的collections模块中的deque实现队列，避免了使用list时的pop(0)操作的时间复杂度问题。同时，为了防止出现负环，记录了每个顶点的入队次数visit_count，当某个顶点的入队次数超过了图的顶点数，说明图中存在负环。