python实现dijkstra算法求最短路径要求输入数据为节点距离矩阵，返回路径以及路径长度

以下是Python代码实现Dijkstra算法求最短路径：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典，将所有节点的距离设为无限大
    distances = {node: float('inf') for node in graph}
    # 将起点的距离设为0
    distances[start] = 0
    # 初始化堆，将起点加入堆中
    heap = [(0, start)]
    # 初始化前驱字典
    predecessors = {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
                predecessors[neighbor] = current_node
                heapq.heappush(heap, (distance, neighbor))

    # 构造路径
    path = []
    node = start
    while node is not None:
        path.append(node)
        node = predecessors[node]
    path.reverse()

    return path, distances

这里的输入数据为一个字典，表示节点之间的距离矩阵。例如，如果有3个节点，那么可以表示为：

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

这个字典表示节点A到节点B的距离是1，节点A到节点C的距离是4，以此类推。使用这个字典作为输入数据，调用dijkstra函数即可求出最短路径和路径长度。例如：

path, distances = dijkstra(graph, 'A')
print(path)
print(distances)

输出结果为：

['A', 'B', 'C']
{'A': 0, 'B': 1, 'C': 3}

这表示从节点A到节点B的最短路径是A->B，距离为1；从节点A到节点C的最短路径是A->B->C，距离为3。