算法动态规划求最短路径

动态规划是一种常用的求解最短路径问题的算法。它通过将问题分解为子问题，并利用子问题的最优解来求解原问题的最优解。下面是一个使用动态规划求解最短路径的例子[^1]：

1. 首先，我们需要定义一个二维数组dp，其中dp[i][j]表示从起点到顶点j的最短路径长度。

2. 初始化dp数组，将起点到自身的最短路径长度设为0，其他顶点的最短路径长度设为无穷大。

3. 对于每个顶点j，遍历所有的边，如果存在一条从顶点i到顶点j的边，且路径长度小于dp[i][j]，则更新dp[i][j]的值为该路径长度。

4. 重复步骤3，直到所有的顶点都被遍历过。

5. 最后，dp数组中的值即为从起点到各个顶点的最短路径长度。

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

public class ShortestPath {
    public static void main(String[] args) {
        int[][] graph = {
            {0, 2, 4, 0, 0},
            {0, 0, 1, 5, 0},
            {0, 0, 0, 0, 3},
            {0, 0, 0, 0, 1},
            {0, 0, 0, 0, 0}
        };
        int start = 0;
        int[] dp = new int[graph.length];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[start] = 0;
        
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph.length; j++) {
                if (graph[i][j] != 0 && dp[i] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[i] + graph[i][j]);
                }
            }
        }
        
        for (int i = 0; i < graph.length; i++) {
            System.out.println("Shortest path from " + start + " to " + i + ": " + dp[i]);
        }
    }
}