- 系列文章目录
- 一、关键路径
- 二、小结
学习来源： 日撸 Java 三百行（31-40天，图） 一、关键路径
- 拓扑排序是关键路径的一部分.
- 关键路径长度, 其实是最远路径长度. 然而, 它并非最短路径的对偶问题. 我尝试修改 Dijkstra 算法来解决, 然后发现自己傻了.
- 正向算每个节点的最早开始时间, 逆向算每个节点的最晚开始时间, 设计太牛了.
代码如下：
package datastructure.graph;
import java.util.Arrays;
import matrix.IntMatrix;
public class Net {
// The maximal distance. Do not use Integer.MAX_VALUE.
public static final int MAX_DISTANCE = 10000;
// The number of nodes.
int numNodes;
// The weight matrix. We use int to represent weight for simplicity.
IntMatrix weightMatrix;
public Net(int paraNumNodes) {
numNodes = paraNumNodes;
weightMatrix = new IntMatrix(numNodes, numNodes);
for (int i = 0; i < numNodes; i++) {
// For better readability, you may need to write fill() in class
// IntMatrix.
Arrays.fill(weightMatrix.getData()[i], MAX_DISTANCE);
} // Of for i
}// Of the first constructor
public Net(int[][] paraMatrix) {
weightMatrix = new IntMatrix(paraMatrix);
numNodes = weightMatrix.getRows();
}// Of the second constructor
@Override
public String toString() {
String resultString = "This is the weight matrix of the graph.rn" + weightMatrix;
return resultString;
}// Of toString
public int[] dijkstra(int paraSource) {
// Step 1. Initialize.
int[] tempDistanceArray = new int[numNodes];
for (int i = 0; i < numNodes; i++) {
tempDistanceArray[i] = weightMatrix.getValue(paraSource, i);
} // Of for i
int[] tempParentArray = new int[numNodes];
Arrays.fill(tempParentArray, paraSource);
// -1 for no parent.
tempParentArray[paraSource] = -1;
// Visited nodes will not be considered further.
boolean[] tempVisitedArray = new boolean[numNodes];
tempVisitedArray[paraSource] = true;
// Step 2. Main loops.
int tempMinDistance;
int tempBestNode = -1;
for (int i = 0; i < numNodes - 1; i++) {
// Step 2.1 Find out the best next node.
tempMinDistance = Integer.MAX_VALUE;
for (int j = 0; j < numNodes; j++) {
// This node is visited.
if (tempVisitedArray[j]) {
continue;
} // Of if
if (tempMinDistance > tempDistanceArray[j]) {
tempMinDistance = tempDistanceArray[j];
tempBestNode = j;
} // Of if
} // Of for j
tempVisitedArray[tempBestNode] = true;
// Step 2.2 Prepare for the next round.
for (int j = 0; j < numNodes; j++) {
// This node is visited.
if (tempVisitedArray[j]) {
continue;
} // Of if
// This node cannot be reached.
if (weightMatrix.getValue(tempBestNode, j) >= MAX_DISTANCE) {
continue;
} // Of if
if (tempDistanceArray[j] > tempDistanceArray[tempBestNode] + weightMatrix.getValue(tempBestNode, j)) {
// Change the distance.
tempDistanceArray[j] = tempDistanceArray[tempBestNode] + weightMatrix.getValue(tempBestNode, j);
// Change the parent.
tempParentArray[j] = tempBestNode;
} // Of if
} // Of for j
// For test
System.out.println("The distance to each node: " + Arrays.toString(tempDistanceArray));
System.out.println("The parent of each node: " + Arrays.toString(tempParentArray));
} // Of for i
// Step 3. Output for debug.
System.out.println("Finally");
System.out.println("The distance to each node: " + Arrays.toString(tempDistanceArray));
System.out.println("The parent of each node: " + Arrays.toString(tempParentArray));
return tempDistanceArray;
}// Of dijkstra
public int prim() {
// Step 1. Initialize.
// Any node can be the source.
int tempSource = 0;
int[] tempDistanceArray = new int[numNodes];
for (int i = 0; i < numNodes; i++) {
tempDistanceArray[i] = weightMatrix.getValue(tempSource, i);
} // Of for i
int[] tempParentArray = new int[numNodes];
Arrays.fill(tempParentArray, tempSource);
// -1 for no parent.
tempParentArray[tempSource] = -1;
// Visited nodes will not be considered further.
boolean[] tempVisitedArray = new boolean[numNodes];
tempVisitedArray[tempSource] = true;
// Step 2. Main loops.
int tempMinDistance;
int tempBestNode = -1;
for (int i = 0; i < numNodes - 1; i++) {
// Step 2.1 Find out the best next node.
tempMinDistance = Integer.MAX_VALUE;
for (int j = 0; j < numNodes; j++) {
// This node is visited.
if (tempVisitedArray[j]) {
continue;
} // Of if
if (tempMinDistance > tempDistanceArray[j]) {
tempMinDistance = tempDistanceArray[j];
tempBestNode = j;
} // Of if
} // Of for j
tempVisitedArray[tempBestNode] = true;
// Step 2.2 Prepare for the next round.
for (int j = 0; j < numNodes; j++) {
// This node is visited.
if (tempVisitedArray[j]) {
continue;
} // Of if
// This node cannot be reached.
if (weightMatrix.getValue(tempBestNode, j) >= MAX_DISTANCE) {
continue;
} // Of if
// Attention: the difference from the Dijkstra algorithm.
if (tempDistanceArray[j] > weightMatrix.getValue(tempBestNode, j)) {
// Change the distance.
tempDistanceArray[j] = weightMatrix.getValue(tempBestNode, j);
// Change the parent.
tempParentArray[j] = tempBestNode;
} // Of if
} // Of for j
// For test
System.out.println("The selected distance for each node: " + Arrays.toString(tempDistanceArray));
System.out.println("The parent of each node: " + Arrays.toString(tempParentArray));
} // Of for i
int resultCost = 0;
for (int i = 0; i < numNodes; i++) {
resultCost += tempDistanceArray[i];
} // Of for i
// Step 3. Output for debug.
System.out.println("Finally");
System.out.println("The parent of each node: " + Arrays.toString(tempParentArray));
System.out.println("The total cost: " + resultCost);
return resultCost;
}// Of prim
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
public static void main(String args[]) {
Net tempNet0 = new Net(3);
System.out.println(tempNet0);
int[][] tempMatrix1 = { { 0, 9, 3, 6 }, { 5, 0, 2, 4 }, { 3, 2, 0, 1 }, { 2, 8, 7, 0 } };
Net tempNet1 = new Net(tempMatrix1);
System.out.println(tempNet1);
// Dijkstra
tempNet1.dijkstra(1);
// An undirected net is required.
int[][] tempMatrix2 = { { 0, 7, MAX_DISTANCE, 5, MAX_DISTANCE }, { 7, 0, 8, 9, 7 },
{ MAX_DISTANCE, 8, 0, MAX_DISTANCE, 5 }, { 5, 9, MAX_DISTANCE, 0, 15, },
{ MAX_DISTANCE, 7, 5, 15, 0 } };
Net tempNet2 = new Net(tempMatrix2);
tempNet2.prim();
// A directed net without loop is required.
// Node cannot reach itself. It is indicated by -1.
int[][] tempMatrix3 = { { -1, 3, 2, -1, -1, -1 }, { -1, -1, -1, 2, 3, -1 }, { -1, -1, -1, 4, -1, 3 },
{ -1, -1, -1, -1, -1, 2 }, { -1, -1, -1, -1, -1, 1 }, { -1, -1, -1, -1, -1, -1 } };
Net tempNet3 = new Net(tempMatrix3);
System.out.println("-------critical path");
tempNet3.criticalPath();
}// Of main
}// Of class Net
二、小结
-
之前学过图，但是用的是C++的STL库，写起来相对简单一点。现在用Java写，很多写法还不习惯，变量名太长了，老是搞忘。
-
还学的不够细致，基本上只过了一遍，在代码实战方面还做得不太好，下来有空多练练题。
-
对图的表示，刚开始光看代码其实很难看懂，但是如果把图画出来，把方法结构理清楚，写代码就容易多了。所以，不要一上来就逮着代码写，扣半天脑壳扣不出来。
-
学的BFS和DFS是其他大型算法的思路和若干个微小的分支，随便改一改又是不同的功能。
-
在Dijkstra算法中的tempVisited数组用来标记元素是否被访问，这个思想值得学习。
-
邻接表、邻接矩阵理解起来相对容易，但是十字链表有一点点难呢。
-
当学习DFS和BFS算法时，代码中的一些if语句可以不写，但是写了的话就起到了保证算法效率的作用，应该相当于是剪枝吧。
-
Huffman、Dijkstra与Prim都有用到贪心的思想，以前接触过贪心，但是有时候还不太能马上理清楚。虽然贪心是三大算法最简单的，但是又因为其可渗透之深入，万物之可贪，所以它的部分算法又是最难找准切入，需要你去细细观察。
-
等到全部过完一遍之后，再来自己写一遍最好，查漏补缺！还有在过的时候最好先搞懂这一小结的代码主要要完成什么样的一个工作，有什么样的流程和思想，才能更好的理解，不然当时懂了，过一会就又忘了！
-
有些东西要自己主动去学习，去吸收。就像学习m着色的时候，就对大体规则很模糊了，光看代码也看得很迷糊，这个时候就开始烦躁了，越烦躁越不想学，然后无限循环。。。所以，还是要有不确定的东西的时候就马上去学习！
