动态规划实现最短路径python代码

以下是使用动态规划实现最短路径的 Python 代码：

def shortest_path(graph, start, end):
    # 初始化距离字典和路径字典
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    paths = {vertex: [] for vertex in graph}
    paths[start] = [start]
    
    # 遍历所有节点
    for _ in range(len(graph) - 1):
        for current_vertex in graph:
            for neighbor, weight in graph[current_vertex].items():
                # 计算到当前节点的距离
                distance = distances[current_vertex] + weight
                # 如果距离更短，则更新距离和路径
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    paths[neighbor] = paths[current_vertex] + [neighbor]
    
    # 返回最短路径和距离
    return paths[end], distances[end]

其中，`graph` 是一个字典，表示图的邻接表；`start` 和 `end` 分别是起点和终点。