图的最短路径算法代码

这里给出Dijkstra算法和Bellman-Ford算法的Python代码实现。

Dijkstra算法代码实现：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    # 初始化堆
    heap = [(start, 0)]
    heapq.heapify(heap)
    while heap:
        # 弹出堆中距离最小的节点
        curr_node, curr_dist = heapq.heappop(heap)
        # 如果当前节点已经访问过，则跳过
        if curr_dist > dist[curr_node]:
            continue
        # 遍历当前节点的相邻节点
        for neighbor, weight in graph[curr_node].items():
            # 计算从起点到相邻节点的距离
            distance = dist[curr_node] + weight
            # 如果计算出的距离比已知的距离更短，则更新距离
            if distance < dist[neighbor]:
                dist[neighbor] = distance
                # 将相邻节点加入堆中
                heapq.heappush(heap, (neighbor, distance))
    return dist

Bellman-Ford算法代码实现：

def bellman_ford(graph, start):
    # 初始化距离字典
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    # 遍历所有边，更新距离
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if dist[node] + weight < dist[neighbor]:
                    dist[neighbor] = dist[node] + weight
    # 检查是否存在负权重环
    for node in graph:
        for neighbor, weight in graph[node].items():
            if dist[node] + weight < dist[neighbor]:
                raise ValueError("存在负权重环")
    return dist

这两个算法的时间复杂度都是$O(ElogV)$，其中$E$是边的数量，$V$是节点的数量。