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"));
}
}
|
