交通图最短路径算法python代码

以下是使用Dijkstra算法求解最短路径的Python代码示例：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典，所有节点的初始距离为无穷大
    distances = {node: float('inf') for node in graph}
    # 将起点的距离设置为0
    distances[start] = 0
    # 使用堆来存储未访问的节点和距离，每次选择距离最小的节点
    heap = [(0, start)]
    # 存储节点的前驱节点，用于最后的路径重构
    previous_nodes = {node: None for node in graph}

    while heap:
        # 取出距离最小的节点
        current_distance, current_node = heapq.heappop(heap)
        # 如果当前节点已经被访问过，则跳过
        if current_distance > distances[current_node]:
            continue
        # 遍历当前节点的邻居节点
        for neighbor, weight in graph[current_node].items():
            # 计算新的距离
            distance = current_distance + weight
            # 如果新的距离比之前的距离更小，则更新距离和前驱节点
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_nodes[neighbor] = current_node
                # 将新的节点加入堆中
                heapq.heappush(heap, (distance, neighbor))

    return distances, previous_nodes

# 示例
graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 8, 'D': 3},
    'F': {'D': 6}
}

distances, previous_nodes = dijkstra(graph, 'A')
print(distances) # 输出：{'A': 0, 'B': 5, 'C': 1, 'D': 6, 'E': 9, 'F': 12}

# 重构路径
path = []
node = 'F'
while node is not None:
    path.append(node)
    node = previous_nodes[node]
path.reverse()
print(path) # 输出：['A', 'C', 'D', 'F']

其中，`graph`表示图的邻接表表示法，`start`表示起点。函数返回两个字典，`distances`存储每个节点到起点的距离，`previous_nodes`存储每个节点的前驱节点。最后可以通过前驱节点字典重构出起点到终点的路径。