Writing in the front

  • Full text of data structure and algorithm

The difference between

  • Dijkstra algorithm, through the selected vertex to be visited, to find the shortest path from the starting vertex to other vertices
  • Freudian algorithm, where each vertex is a starting point, finds the shortest path from each vertex to the other vertices

Shortest path problem (Dijkstra algorithm)

  • It is used to calculate the shortest path from one node to other nodes, which is mainly characterized by layer-by-layer expansion with the starting point as the center, and the breadth-first search idea is applied until the extension reaches the end point
  • call
char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; int[][] matrix = new int[vertex.length][vertex.length]; final int N = 65535; Matrix [0] = new int[]{N, 5, 7, N, N, 6}; matrix[1] = new int[]{5, N, N, 9, N, N, 3}; matrix[2] = new int[]{7, N, N, N, 8, N, N}; matrix[3] = new int[]{N, 9, N, N, N, 4, N}; matrix[4] = new int[]{N, N, 8, N, N, 5, 4}; matrix[5] = new int[]{N, N, N, 4, 5, N, 6}; matrix[6] = new int[]{5, 3, N, N, 4, 6, N}; Graph graph = new Graph(vertex, matrix); graph.showGraph(); graph.dsj(3);Copy the code
  • Figure class
class Graph { private char[] vertex; Private int[][] matrix; Private VisitedVertex vv; Public Graph(char[] vertex, int[][] matrix) {this.vertex = vertex; this.matrix = matrix; } public void showGraph() { for (int[] ints : matrix) { System.out.println(Arrays.toString(ints)); Public void DSJ (int index) {vv = new VisitedVertex(vertex. Length, index); update(index); Int adjoinPoint; // Update the distance between index and surrounding vertices. for (int i = 1; i < vertex.length; i++) { adjoinPoint = vv.updateArr(); // Select and return a new access vertex update(adjoinPoint); } vv.show(); } private void update (int index) {int len = 0; For (int j = 0; j < matrix[index].length; J ++) {len = vv.getdis (index) + matrix[index][j]; // If len is less than the distance from the starting vertex to the j vertex, update if (! vv.in(j) && len < vv.getDis(j)) { vv.updatePre(j, index); Vv. updateDis(j, len); // Update the distance from the starting vertex to the j-vertex}}}}Copy the code
  • Top class
class VisitedVertex { public int[] already_arr; Public int[] pre_visited; Public int[] dis; // Record the distance from one vertex to all other vertices, Public VisitedVertex(int length) public VisitedVertex(int length) public VisitedVertex(int length) int index) { this.already_arr = new int[length]; this.pre_visited = new int[length]; this.dis = new int[length]; // Initialize dis Arrays. Fill (dis, 65535); This.already_arr [index] = 1; This. dis[index] = 0; } public Boolean in(int index) {return already_arr[index] == 1;} public Boolean in(int index) {return already_arr[index] == 1; } public void updateDis(int index, int len) {dis[index] = len; } public void updatePre(int pre, int index) {pre_visited[pre] = index; } public int getDis(int index) {return dis[index]; } public int updateArr() {int min = 65535; int index = 0; for (int i = 0; i < already_arr.length; i++) { if (already_arr[i] == 0 && dis[i] < min) { min = dis[i]; index = i; Already_arr [index] = 1; return index; Public void show() {system.out.println (array.toString (already_arr)); System.out.println(Arrays.toString(pre_visited)); System.out.println(Arrays.toString(dis)); }}Copy the code

parsing

  • The following parsing revolves around the core method explanation
public void dsj (int index) { vv = new VisitedVertex(vertex.length, index); update(index); Int adjoinPoint; // Update the distance between index and surrounding vertices. for (int i = 1; i < vertex.length; i++) { adjoinPoint = vv.updateArr(); // Select and return a new access vertex update(adjoinPoint); } vv.show(); } public int updateArr() {int min = 65535; int index = 0; for (int i = 0; i < already_arr.length; i++) { if (already_arr[i] == 0 && dis[i] < min) { min = dis[i]; index = i; Already_arr [index] = 1; return index; }Copy the code

The dis array in the vV object is the starting point of index, which means that after the initialization, the dis array in the VV object is the starting point of index, which means that the distance from index to some other point, for example, dis[0] means the distance from index-> 0, no matter how many points are passed in between, Save is the minimum path, and this minimum path is multiple judgments, will be analyzed below

Update (index); , scans index and records the distance of its immediate adjacency. len = vv.getDis(index) + matrix[index][j]; Vv.getdis (index) = 0, vv.getdis (index) = 0, vv.getdis (index) = 0 After this round of judgment, all non-adjacencies are 65535, and all adjacencies have distance values

In the second step, the index adjacency is scanned and the adjacency is scanned as the next layer. UpdateArr method, through already_arr [I] = = 0 && dis [I] < min judgment, first of all, the point is not being accessed, the thought of combining breadth traversal, dis [I] < min to ensure this can be accessed. The accessible point means that the initial value of min is 65535. Once less than 65535, it means that this point is the point that has been visited. This point is explained in combination with the third step. Len = vv.getdis (index) + matrix[index][J]; len = vv.getdis (index) + matrix[index][J]; Vv. getDis(index) = index + + index + index + index + index + index + index If the initial index is G, and G is only adjacent to A and B, then the second step is to scan the adjacent points of A and B. If A is scanned to C, then the distance of G-a-C is vv.getdis (A) (the distance from G to A) +matrix[A][C] (the distance between A and C). The most important thing is that dis[C] also has a value, and the value <65535, dis array is initially initialized to 65535

Dis [I]

In the algorithm, the minimum path is judged twice. For example, if the goal is to find the minimum path G can access only A and C, there are two paths G-A=4, G-C=1, and dis[A]=4, dis[C]=1. Then, in the second step, in the updateArr method, In the for loop, there is A layer of if that determines dis[I]

So, the updateArr for loop ensures that each new access node is the closest to the index, which is the closest to the index. The update does not change the distance between the index and the index, but only updates the distance between the index and the index. So, there is a problem. For example, suppose that g-a =4 g-c-b-a =3, which means that dis[A]=10 dis[C]=1, but in step 2, only C can be used as the new access node. Dis [A]=3, then scan A, but at this point g-a =4, can not replace the original dis[A]; In the second example, g-a =4, g-c =5, the next point to visit is obviously A. G-a is smaller than G-C, so no matter how you visit it, G-A is always the shortest path from G to A, so you can mark A as visited.

Shortest Path problem (Freudian algorithm)

  • The shortest path between vertices
  • call
char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
int[][] matrix = new int[vertex.length][vertex.length];
final int N = 65535;
matrix[0] = new int[]{0, N, 7, N, N, N, N};
matrix[1] = new int[]{N, 0, N, 9, N, N, 3};
matrix[2] = new int[]{7, N, 0, N, 8, N, N};
matrix[3] = new int[]{N, 9, N, 0, N, 4, N};
matrix[4] = new int[]{N, N, 8, N, 0, 5, 4};
matrix[5] = new int[]{N, N, N, 4, 5, 0, 6};
matrix[6] = new int[]{N, 3, N, N, 4, 6, 0};
Graph graph = new Graph(vertex.length, matrix, vertex);
graph.showGraph();
graph.floyd();
graph.showGraph();
Copy the code
  • figure
class Graph { private char[] vertex; // Store vertex array; private int[][] dis; Private int[][] pre; private int[] pre; Public void Floyd () {int len = 0; For (int k = 0; for (int k = 0; k < vertex.length; K++) {for (int I = 0; i < vertex.length; Int j = 0; int j = 0; j < vertex.length; j++) { len = dis[i][k] + dis[k][j]; / / and I - k k - j if (len < dis [I] [j]) {/ / less than direct distance dis [I] [j] = len; / / pre [k] [j] the k line the j column elements, the first is its own pre [I] [j] = pre [k] [j]; Public Graph(int length, int length)}}}}} /** * @param * @param martix * @param vertex */ int[][] martix, char[] vertex) { this.vertex = vertex; this.dis = martix; this.pre = new int[length][length]; For (int I = 0; for (int I = 0; i < length; i++) { Arrays.fill(pre[i], i); } } public void showGraph() { for (int i = 0; i < vertex.length; i++) { for (int j = 0; j < vertex.length; j++) { System.out.print(vertex[i] + "-" + vertex[pre[i][j]] + "-" + vertex[j] + " "); } System.out.println(); } System.out.println("------------------"); for (int i = 0; i < vertex.length; i++) { for (int j = 0; j < vertex.length; j++) { System.out.print(vertex[i] + "-" + vertex[pre[i][j]] + "-" + vertex[j] + "-" + dis[i][j] + " "); } System.out.println(); } System.out.println("------------------"); }}Copy the code

summary

For example, if the path of B-A is only B-G-e-c-A, then if the outermost loop is the starting vertex, the traversal sequence will be B-B-G b-c-A b-e-C b-G-A b-G-C. In this order, The path B-A can never be found. The outermost layer of the path is the middle vertex, which ensures that the path from the starting vertex to the ending vertex can be scanned. If the path a-C is only A-G-b-d-F-e-c and the sequence scan is A-A-G g-b-d g-D-F F-E-c g-F-C, then a-G-C can be obtained. That is to say, no matter what path, as long as the middle vertex is in the outermost layer and the starting point and ending point are fully traversed, You can find a path between any point and connect it by switching the middle vertices

pre[i][j] = pre[k][j]; What that means is that you take the back half of the precursor node as the new precursor node