使用动态规划法求单源最短路径问题

动态规划法可以用来解决单源最短路径问题。其基本思想是利用子问题的最优解来求解原问题的最优解。具体来说，我们可以定义一个状态数组dp，其中dp[i]表示从源点s到顶点i的最短路径长度。然后，我们可以通过状态转移方程来更新dp数组的值，即dp[i] = min(dp[i], dp[j] + w(j, i))，其中w(j, i)表示从顶点j到顶点i的边权值。最后，dp[n]就是从源点s到顶点n的最短路径长度。

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

def shortest_path(graph, s):
    n = len(graph)
    dp = [float('inf')] * n
    dp[s] = 0
    for i in range(n):
        for j in range(n):
            if graph[j][i] != 0:
                dp[i] = min(dp[i], dp[j] + graph[j][i])
    return dp[n-1]

# 示例图
graph = [[0, 10, 0, 30, 100],
         [0, 0, 50, 0, 0],
         [0, 0, 0, 0, 10],
         [0, 0, 20, 0, 60],
         [0, 0, 0, 0, 0]]

# 求从顶点0到顶点4的最短路径长度
print(shortest_path(graph, 0)) # 输出：40