Java学习-Day20

关键路径

一、描述

拓扑排序是关键路径的一部分. 为什么会有这种说法呢？就像工程施工需要把所有前置条件完成才能继续, 这个所谓前置条件就是拓扑排序. 而关键路径要求的就是完成工程的最长时间.

关键路径长度, 其实是最远路径长度. 然而, 它并非最短路径的对偶问题.

正向算每个节点的最早开始时间, 逆向算每个节点的最晚开始时间. 当最早开始和最晚开始为一样的时候就说明这个节点是关键路径中的一个节点, 找出所有这样的节点连接起来就是关键路径.

二、求解

1. 思路

正向拓扑排序求最早开始时间, 逆向拓扑排序求最晚开始时间.

2. 具体代码

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
/**
 *********************
 * Critical path. Net validity checks such as loop check not implemented. The
 * source should be 0 and the destination should be n-1.
 *
 * @return The node sequence of the path.
 *********************
 */
public boolean[] criticalPath() {
	// One more value to save simple computation.
	int tempValue;

	// Step 1. The in-degree of each node.
	int[] tempInDegrees = new int[numNodes];
	for (int i = 0; i < numNodes; i++) {
		for (int j = 0; j < numNodes; j++) {
			if (weightMatrix.getValue(i, j) != -1) {
				tempInDegrees[j]++;
			} // Of if
		} // Of for j
	} // Of for i
	System.out.println("In-degree of nodes: " + Arrays.toString(tempInDegrees));

	// Step 2. Topology sorting.
	int[] tempEarliestTimeArray = new int[numNodes];
	for (int i = 0; i < numNodes; i++) {
		// This node cannot be removed.
		if (tempInDegrees[i] > 0) {
			continue;
		} // Of if

		System.out.println("Removing " + i);

		for (int j = 0; j < numNodes; j++) {
			if (weightMatrix.getValue(i, j) != -1) {
				tempValue = tempEarliestTimeArray[i] + weightMatrix.getValue(i, j);
				if (tempEarliestTimeArray[j] < tempValue) {
					tempEarliestTimeArray[j] = tempValue;
				} // Of if
				tempInDegrees[j]--;
			} // Of if
		} // Of for j
	} // Of for i

	System.out.println("Earlest start time: " + Arrays.toString(tempEarliestTimeArray));

	// Step 3. The out-degree of each node.
	int[] tempOutDegrees = new int[numNodes];
	for (int i = 0; i < numNodes; i++) {
		for (int j = 0; j < numNodes; j++) {
			if (weightMatrix.getValue(i, j) != -1) {
				tempOutDegrees[i]++;
			} // Of if
		} // Of for j
	} // Of for i
	System.out.println("Out-degree of nodes: " + Arrays.toString(tempOutDegrees));

	// Step 4. Reverse topology sorting.
	int[] tempLatestTimeArray = new int[numNodes];
	for (int i = 0; i < numNodes; i++) {
		tempLatestTimeArray[i] = tempEarliestTimeArray[numNodes - 1];
	} // Of for i

	for (int i = numNodes - 1; i >= 0; i--) {
		// This node cannot be removed.
		if (tempOutDegrees[i] > 0) {
			continue;
		} // Of if

		System.out.println("Removing " + i);

		for (int j = 0; j < numNodes; j++) {
			if (weightMatrix.getValue(j, i) != -1) {
				tempValue = tempLatestTimeArray[i] - weightMatrix.getValue(j, i);
				if (tempLatestTimeArray[j] > tempValue) {
					tempLatestTimeArray[j] = tempValue;
				} // Of if
				tempOutDegrees[j]--;
				System.out.println("The out-degree of " + j + " decreases by 1.");
			} // Of if
		} // Of for j
	} // Of for i

	System.out.println("Latest start time: " + Arrays.toString(tempLatestTimeArray));

	boolean[] resultCriticalArray = new boolean[numNodes];
	for (int i = 0; i < numNodes; i++) {
		if (tempEarliestTimeArray[i] == tempLatestTimeArray[i]) {
			resultCriticalArray[i] = true;
		} // Of if
	} // Of for i

	System.out.println("Critical array: " + Arrays.toString(resultCriticalArray));
	System.out.print("Critical nodes: ");
	for (int i = 0; i < numNodes; i++) {
		if (resultCriticalArray[i]) {
			System.out.print(" " + i);
		} // Of if
	} // Of for i
	System.out.println();

	return resultCriticalArray;
}// Of criticalPath

3. 运行截图

总结

  1. 图在写过的数据结构中应该算一个比较稀有的存在, 能在实际代码中使用上树的结构就已经是个非常了不起的突破了. 所以在这部分内容中写代码前就是把图画出来然后在转成数组的结构. (其实还是代码写得少. 要是做个地图类的软件, 图的使用就是非常必要的了)

  2. 把图转换为矩阵是真的非常精妙的想法, 难道是由向量这个演化而来? 无论怎么说这一操作降低了存储难度但在一定程度上增加了 Debug 的难度.

  3. 这一部分也是经典算法频出的一部分, 尤其是深度优先和广度优先算法, 这不仅仅可以运用于图还可以运用于树形结构. 其中关键在于数据结构的巧妙结合, 宏观来看也不过是暴力破解.

  4. 在遍历的过程中有一个标记的过程值得注意. 这样整个算法就很模拟现实世界. 就好像我去过那个地方我就不再去了.

  5. 动态规划和贪心算法也是在这些算法中被使用的部分, 不断根据当前环境更改自己的值, 选择当前环境下最优的解法.

  6. 图的算法相比起之前学过的算法不是那么直观, 无论是遍历还是找出路径. 在之前的代码中无非就是增删改查, 在这部分更重要的是找到一条路径, 增删改仿佛在图这就不是那么的重要. 无论怎么说图更贴近生活是无论如何都需要掌握的一部分.

  7. 在编码方面最难注意到的就是矩阵下标, 然后在邻接矩阵中的数值表示为权值的时候就更加的混乱. 循环的终止刚开始也弄不清楚.

  8. 比起代码更重要的是思想, 我可以两次得出一样的思路, 但是我绝不可能两次写出一样的代码. 记忆代码是件非常难受的事情, 还是理清思路才是王道.

  9. 学习的过程是个重复, 即使在图这部分还是用到了之前所学过的栈、队列和链表等东西. 第一次写博客哪能那么尽善尽美, 常看常新留给自己.

  10. 有序的思考, 完整的公式往往比灵感迸发写出来的代码更容易通过. 灵感仅仅做为尝试, 万万不能做为解题的良方.