【运筹优化】最短路算法之动态规划算法 + Java代码实现_实时运筹优化 算法

---

一、java代码

public class DP {
    // 距离矩阵
    double[][] distance;
    // 起点
    int start;
    // 终点
    int end;
    // 记录起点到终点途中每个点的最短距离
    double[] dp;

    /**
     * @param distance
     * @param start
     * @param end
     * @Description 构造函数
     * @Author WSKH
     */
    public DP(double[][] distance, int start, int end) {
        this.distance = distance;
        this.start = start;
        this.end = end;
    }

    /**
     * @Description 进行求解
     * @Author WSKH
     */
    public void solve() {
        dp = new double[distance.length];
        Arrays.fill(dp,Double.MAX_VALUE);
        getMinLen(end);
        System.out.println(Arrays.toString(dp));
        System.out.println("最短路程长度为："+dp[end]);
    }

    /**
     * @param end 终点索引
     * @Description 获取起点到终点的最长路径
     * @Author WSKH
     */
    public double getMinLen(int end) {
        if(end==start){
            dp[start] = 0;
            return 0;
        }
        double min = Double.MAX_VALUE;
        for (int i = 0; i < distance.length; i++) {
            // 如果i点可以去到end点
            if (i != end && distance[i][end] != Double.MAX_VALUE) {
                if (dp[i] != Double.MAX_VALUE) {
                    min = Math.min(min, dp[i] + distance[i][end]);
                } else {
                    min = Math.min(min, getMinLen(i) + distance[i][end]);
                }
            }
        }
        dp[end] = min;
        return min;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

二、测试

public class Test {
    public static void main(String[] args) {
        double[][] distance = new double[][]{
                {0,5,6,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE},
                {Double.MAX_VALUE,0,Double.MAX_VALUE,Double.MAX_VALUE,3,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE},
                {Double.MAX_VALUE,Double.MAX_VALUE,0,3,6,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE},
                {Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,0,3,Double.MAX_VALUE,1,4,Double.MAX_VALUE,Double.MAX_VALUE},
                {Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,0,4,2,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE},
                {Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,0,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,4},
                {Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,0,Double.MAX_VALUE,5,Double.MAX_VALUE},
                {Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,0,2,Double.MAX_VALUE},
                {Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,0,2},
                {Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,0}
        };
        new DP(distance,0,9).solve();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

控制台输出：

[0.0, 5.0, 6.0, 9.0, 8.0, 12.0, 10.0, 13.0, 15.0, 16.0]
最短路程长度为：16.0
1
2

注意：此算法只适用于无环图