python实现Dijkstra算法并给出示例输入和输出

Dijkstra算法是一种用于图中寻找最短路径的算法，其基本思想是从起点开始，逐步扩展路径，直到到达终点为止。在扩展路径的过程中，会不断更新节点的最短路径和前驱节点。

下面给出Python实现Dijkstra算法的示例代码和输入输出：

示例输入：

图的邻接矩阵表示：

0 10 inf inf inf
inf 0 5 inf inf
inf inf 0 1 inf
inf inf inf 0 7
inf inf inf inf 0

起点和终点：

start = 0
end = 4

示例输出：

Shortest distance from 0 to 4 is 8
Path: [0, 1, 2, 3, 4]

示例代码：

import heapq

# Dijkstra算法
def dijkstra(graph, start, end):
    # 初始化距离和前驱节点
    dist = [float('inf')] * len(graph)
    dist[start] = 0
    prev = [-1] * len(graph)
    
    # 将起点加入堆中
    heap = [(0, start)]
    
    while heap:
        # 弹出堆顶节点
        (d, u) = heapq.heappop(heap)
        if u == end:
            # 到达终点，退出循环
            break
        
        # 遍历相邻节点
        for i, weight in enumerate(graph[u]):
            if weight != float('inf'):
                # 计算新的距离
                new_dist = dist[u] + weight
                if new_dist < dist[i]:
                    # 更新距离和前驱节点
                    dist[i] = new_dist
                    prev[i] = u
                    
                    # 将节点加入堆中
                    heapq.heappush(heap, (new_dist, i))
    
    # 构造路径
    path = []
    u = end
    while prev[u] != -1:
        path.insert(0, u)
        u = prev[u]
    path.insert(0, u)
    
    # 返回最短距离和路径
    return dist[end], path

# 测试
graph = [
    [0, 10, float('inf'), float('inf'), float('inf')],
    [float('inf'), 0, 5, float('inf'), float('inf')],
    [float('inf'), float('inf'), 0, 1, float('inf')],
    [float('inf'), float('inf'), float('inf'), 0, 7],
    [float('inf'), float('inf'), float('inf'), float('inf'), 0]
]
start = 0
end = 4
dist, path = dijkstra(graph, start, end)
print(f"Shortest distance from {start} to {end} is {dist}")
print(f"Path: {path}")