python利用动态规划求最短路径

动态规划是一种用来解决最优化问题的算法，通常用于求解最短路径等问题。在求解最短路径时，可以使用动态规划的思想。

下面是一个示例代码，展示了如何使用动态规划求解最短路径：

# 定义一个矩阵，表示路径的权重
matrix = [
    [0, 2, 4, 1],
    [2, 0, 3, 2],
    [4, 3, 0, 4],
    [1, 2, 4, 0]
]

# 定义起点和终点
start = 0
end = 3

# 定义一个数组，用于保存到每个点的最短路径
# 初始值为无穷大
shortest_path = [float('inf')] * len(matrix)

# 起点到自己的最短路径为0
shortest_path[start] = 0

# 使用动态规划求解最短路径
for i in range(1, len(matrix)):
    for j in range(len(matrix)):
        for k in range(len(matrix)):
            if shortest_path[j] + matrix[j][k] < shortest_path[k]:
                shortest_path[k] = shortest_path[j] + matrix[j][k]

# 输出最短路径
print(f"The shortest path from {start} to {end} is {shortest_path[end]}.")

在这个示例代码中，我们定义了一个矩阵来表示路径的权重，然后定义了起点和终点。我们使用一个数组来保存到每个点的最短路径，初始值为无穷大。然后，我们把起点到自己的最短路径设为0，使用动态规划求解最短路径。最后，输出起点到终点的最短路径。