动态规划求最短路径

动态规划是一种常用的求解最短路径问题的方法。下面是一个使用动态规划求解最短路径的示例[^1]：

1. 首先，我们需要定义一个二维数组dp，其中dp[i][j]表示从起点到达顶点i的路径中，经过的顶点的最小权值和。

2. 初始化dp数组，将所有元素初始化为无穷大，除了起点的dp值为0。

3. 对于每个顶点i，遍历其所有的邻居顶点j，更新dp[j]的值为dp[i]加上从顶点i到顶点j的权值。

4. 重复步骤3，直到所有顶点的dp值都被更新。

5. 最后，dp数组中的最后一个元素即为从起点到终点的最短路径的权值和。

下面是一个使用动态规划求解最短路径的Python代码示例：

def shortest_path(graph, start, end):
    # 初始化dp数组
    dp = [float('inf')] * len(graph)
    dp[start] = 0

    # 动态规划求解最短路径
    for i in range(start, end + 1):
        for j in range(len(graph[i])):
            if dp[i] + graph[i][j] < dp[j]:
                dp[j] = dp[i] + graph[i][j]

    return dp[end]

# 示例图的邻接矩阵表示
graph = [
    [0, 2, 4, 1],
    [2, 0, 1, 5],
    [4, 1, 0, 3],
    [1, 5, 3, 0]
]

start = 0  # 起点
end = 3  # 终点

# 求解最短路径
result = shortest_path(graph, start, end)
print("最短路径的权值和为:", result)  # 输出：最短路径的权值和为: 3