动态规划最短路径问题的代码

动态规划通常用于解决最短路径问题，比如经典的Dijkstra算法或Floyd-Warshall算法。这里我将以Python为例，展示如何使用动态规划解决最简单的情况——单源最短路径问题，假设图中的边是有权的。

使用Floyd-Warshall算法（适用于任意图），其核心思想是通过迭代计算所有节点对之间的最短路径：

def floyd_warshall(graph):
    n = len(graph)
    # 初始化距离矩阵，第一行和列的值为0（表示起点到自身距离为0）
    dist = [[0 if i == j else graph[i][j] for j in range(n)] for i in range(n)]
    
    # 对于所有的中间节点i，更新它到其他所有节点的距离
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # 如果通过k作为中转比直接相连更短，则更新dist[i][j]
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# 示例图，二维列表表示邻接矩阵
graph = [
    [0, 4, 0, 0],
    [4, 0, 8, 0],
    [0, 8, 0, 7],
    [0, 0, 7, 0]
]

shortest_paths = floyd_warshall(graph)

在这个例子中，`shortest_paths`就是从起点到终点的最短路径矩阵。每个`shortest_paths[i][j]`给出了起点到终点j的最短路径长度。