python 最短路径

Python 中可以使用 Dijkstra 算法或者 A* 算法来求解最短路径。

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

import heapq

def dijkstra(graph, start, end):
    # 初始化距离和前驱节点字典
    distance = {node: float('inf') for node in graph}
    predecessor = {node: None for node in graph}
    distance[start] = 0  # 起点距离为 0

    # 存储未遍历节点的优先队列
    unvisited_queue = [(dist, node) for node, dist in distance.items()]
    heapq.heapify(unvisited_queue)

    while unvisited_queue:
        # 获取距离最小的节点
        curr_dist, curr_node = heapq.heappop(unvisited_queue)

        # 如果当前节点已经遍历过，则跳过
        if curr_dist > distance[curr_node]:
            continue

        # 遍历当前节点的邻居
        for neighbor, weight in graph[curr_node].items():
            path = distance[curr_node] + weight
            # 如果当前路径比已知路径更短，则更新距离和前驱节点
            if path < distance[neighbor]:
                distance[neighbor] = path
                predecessor[neighbor] = curr_node
                heapq.heappush(unvisited_queue, (path, neighbor))

        # 如果已经到达终点，则跳出循环
        if curr_node == end:
            break

    # 构建最短路径
    path = []
    curr_node = end
    while curr_node:
        path.append(curr_node)
        curr_node = predecessor[curr_node]
    path.reverse()

    return path, distance[end]

其中，graph 是一个邻接字典，表示图的结构。例如，对于以下图：

A --3-- B --2-- D
 \      |      /
  \     |     /
   1    1    1
    \   |   /
     \  |  /
      C--4--E

可以构建如下邻接字典：

graph = {
    'A': {'B': 3, 'C': 1},
    'B': {'A': 3, 'C': 1, 'D': 2},
    'C': {'A': 1, 'B': 1, 'D': 1, 'E': 4},
    'D': {'B': 2, 'C': 1, 'E': 1},
    'E': {'C': 4, 'D': 1}
}

然后，可以使用 `dijkstra(graph, 'A', 'E')` 来求解从节点 A 到节点 E 的最短路径。