目录

DAG最短路

题目

问题很简单:给定一个城市的地图,所有的道路都是单行道,而且不会构成环。每条道路都有过路费,问您从S点到T点花费的最少费用。 https://gitee.com/lienhui68/picStore/raw/master/null/20200701225229.png

解题思路

回想下DP的两个性质:

  • 无后效性:对于点P,一旦${f(P)}$确定,以后就只关心${f(P)}$的值,不关心怎么去的。  
  • 最优子结构:对于P,我们当然只关心到P的最小费用,即${f(P)}$。如果我们从S走到T是S->P->Q->T,那肯定S走到Q的最优路径是S->P->Q。对一条最优的路径而言,从S走到沿途上所有的点(子问题)的最优路径,都是这条大路的一部分。这个问题的最优子结构性质是显然的。

既然这两个性质都满足,那么本题可以DP。式子明显为: ${f(P)=min{f(R)+w_{R->P}}}$, 其中R为有路通到P的所有的点,$w_{R->P}$为R到P的过路费。

代码实现也很简单,拓扑排序即可。

代码实现

主要属性

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 /**
     * 图的邻接矩阵表现形式
     */
    private int[][] matrix;

    /**
     * 顶点的表现形式
     */
    private List<String> vertexNames;

    /**
     * 入度
     */
    private int[] inDegree;

    /**
     * 最优路径下的当前节点i的前一个坐标,不包括终点,数组长度n-1
     */
    private int[] pre;

    /**
     * 表示到某个顶点的最少费用
     */
    private int[] fee;

核心代码

 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
/**
     * 拓补排序(使用bfs),使用动态规划
     * <p>
     * 保证起点的入度为0且只有一个入度为0的情况, 否则起点出队需要处理起点的子节点的出度情况
     */
    public void dp() {
        Queue<Integer> queue = new LinkedList();
        // 入度为0的顶点入队
        for (int i = 0; i < matrix.length; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        Integer cur;
        while ((cur = queue.poll()) != null) {// 出队
            // 处理费用以及最佳路径
            if (cur != 0) {
                fee[cur] = Integer.MAX_VALUE;
                pre[cur] = -1;
                int pathFee = 0;
                // 找到所有cur的子节点
                if (cur == 3) {
                    System.out.println();
                }
                for (int i = 0; i < vertexNames.size(); i++) {
                    pathFee = matrix[i][cur];
                    // 有指向关系并且满足最优解则进行记录
                    // F(P)=min{}F(R) + w(R->P)}, F(R)表示通向P的所有点,w(R->P)表示R-P的过路费
                    if (pathFee > 0 && fee[i] + pathFee < fee[cur]) {
                        // 汇总最少费用
                        fee[cur] = fee[i] + pathFee;
                        // 记录cur的前一个路径i
                        pre[cur] = i;
                    }
                }
            }
            if (vertexNames.get(cur).equals("T")) {
                // 找到终点,退出
                return;
            }
            // 处理排序
            for (int j = 0; j < matrix[cur].length; j++) {
                if (matrix[cur][j] > 0) {
                    // 将被当前节点指向的节点入度-1
                    inDegree[j]--;
                    // 如果入度降为0则入队
                    if (inDegree[j] == 0) {
                        queue.offer(j);
                    }
                }
            }
        }
    }

完整代码

  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
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
package com.eh.ftd.dsa.ds;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 带权有向图
 *
 * @author David Li
 * @create 2020/07/01 21:20
 */
public class PriorityDAG {
    /**
     * 图的邻接矩阵表现形式
     */
    private int[][] matrix;

    /**
     * 顶点的表现形式
     */
    private List<String> vertexNames;

    /**
     * 入度
     */
    private int[] inDegree;

    /**
     * 最优路径下的当前节点i的前一个坐标,不包括终点,数组长度n-1
     */
    private int[] pre;

    /**
     * 表示到某个顶点的最少费用
     */
    private int[] fee;

    /**
     * 构造器
     *
     * @param vertexNames 顶点名称数组
     */
    public PriorityDAG(String[] vertexNames, int[][] matrix) {
        this.matrix = matrix;
        this.vertexNames = Arrays.asList(vertexNames);
        inDegree = new int[vertexNames.length];
        pre = new int[vertexNames.length];
        // 初始化入度
        for (int[] parent : matrix) {
            for (int j = 0; j < parent.length; j++) {
                if (parent[j] > 0) {
                    inDegree[j]++;
                }
            }
        }
        // 初始化最少费用
        fee = new int[vertexNames.length];
        fee[0] = 0; // 起点费用为0
    }

    private int getIndexByVertexName(String vertexName) {
        for (int i = 0; i < vertexNames.size(); i++) {
            if (vertexName.equals(vertexNames.get(i))) {
                return i;
            }
        }
        throw new RuntimeException();
    }

    /**
     * 拓补排序(使用bfs),使用动态规划
     * <p>
     * 保证起点的入度为0且只有一个入度为0的情况, 否则起点出队需要处理起点的子节点的出度情况
     */
    public void dp() {
        Queue<Integer> queue = new LinkedList();
        // 入度为0的顶点入队
        for (int i = 0; i < matrix.length; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        Integer cur;
        while ((cur = queue.poll()) != null) {// 出队
            // 处理费用以及最佳路径
            if (cur != 0) {
                fee[cur] = Integer.MAX_VALUE;
                pre[cur] = -1;
                int pathFee = 0;
                // 找到所有cur的子节点
                if (cur == 3) {
                    System.out.println();
                }
                for (int i = 0; i < vertexNames.size(); i++) {
                    pathFee = matrix[i][cur];
                    // 有指向关系并且满足最优解则进行记录
                    // F(P)=min{}F(R) + w(R->P)}, F(R)表示通向P的所有点,w(R->P)表示R-P的过路费
                    if (pathFee > 0 && fee[i] + pathFee < fee[cur]) {
                        // 汇总最少费用
                        fee[cur] = fee[i] + pathFee;
                        // 记录cur的前一个路径i
                        pre[cur] = i;
                    }
                }
            }
            if (vertexNames.get(cur).equals("T")) {
                // 找到终点,退出
                return;
            }
            // 处理排序
            for (int j = 0; j < matrix[cur].length; j++) {
                if (matrix[cur][j] > 0) {
                    // 将被当前节点指向的节点入度-1
                    inDegree[j]--;
                    // 如果入度降为0则入队
                    if (inDegree[j] == 0) {
                        queue.offer(j);
                    }
                }
            }
        }
    }

    public void printMatrix() {
        for (int[] arr : matrix) {
            System.out.print("[\t");
            for (int i = 0; i < arr.length; i++) {
                    System.out.printf("%d\t", arr[i]);
            }
            System.out.println("]");
        }
    }

    private void printTheOptPath(int idx) {
        if (idx == 0) {
            System.out.print(0 + " ");
            return;
        }
        printTheOptPath(pre[idx]);
        System.out.printf(idx + " ");
    }


    public static void main(String[] args) {
        String[] vertexNames = {"S", "A", "B", "C", "D", "T"};
        int[][] matrix = {
                {0, 10, 20, 0, 0, 0},
                {0, 0, 0, 30, 10, 0},
                {0, 0, 0, 0, 20, 0},
                {0, 0, 0, 0, 5, 20},
                {0, 0, 0, 0, 0, 10},
                {0, 0, 0, 0, 0, 0}
        };
        PriorityDAG graph = new PriorityDAG(vertexNames, matrix);
        System.out.println("DAG如下:");
        graph.printMatrix();
        graph.dp();
        System.out.printf("最少费用:%d\n", graph.fee[graph.getIndexByVertexName("T")]);
        System.out.print("最佳路径: ");
        graph.printTheOptPath(graph.getIndexByVertexName("T"));
    }
}

运行结果

https://gitee.com/lienhui68/picStore/raw/master/null/20200701230808.png