Shulou(Shulou.com)06/02 Report--

This article mainly explains "the example introduction of java Freudian algorithm and Dijstra algorithm". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "the example introduction of java Freud algorithm and Dijstra algorithm".

The shortest path

Buses and subways are the most common means of transportation, but there are usually a variety of travel options to go somewhere, some with less transfer, some with short time, some with less walking, and so on. This involves the question of how to find the most suitable path, such as how to get to v8 as quickly as possible, starting from v0 in the figure below.

To find the shortest path, there are usually two classical algorithms, which we will introduce one by one.

Dijstra (Dijkstra) algorithm

The idea of Dijstra algorithm is to start from the starting point, find the shortest distance from it to each intermediate point, and approach the end point step by step. Let's take the above figure as an example to demonstrate the process of the Dijstra algorithm.

First of all, starting from v0, the nearest point that can be reached is v1, and the distance is 1, so the first edge through is (v0, v1), as follows:

Next, because v1 can go to v2, v3 and v4, the distance from v0-> v1-> v2 is 4, the distance from v0-> v1-> v3 is 8, and the distance from v0-> v1-> v4 is 6. The shortest of the three paths is v0-> v1-> v2, which is even shorter than directly from v0-> v2, so the next path should be v0-> v1-> v2:

Next, we can get more path information. The distance from v0-> v2-> v4 is 5, and the distance from v0-> v2-> v5 is 11, and the former is shorter than that from v0-> v1-> v4, so the next path should be v0-> v2-> v4, where v0-> v2 is actually v0-> v1-> v2, as shown below:

Next, according to the same logic, the nearest vertex from v4 is v3, the path length is 7, and the direct distance from v0-> v1-> v3 is 8, so the complete path is v0-> v1-> v2-> v4-> v3, as shown below:

In the same way, we can get the following path, which is the shortest path we are looking for, as follows:

It can be seen that the Dijstra algorithm approaches the end point little by little by constantly finding the shortest distance to the middle vertex and comparing the direct distance between the vertices, which is more suitable for planning the route in advance, rather than looking at it step by step.

Freud's (Floyd) algorithm

The Freudian algorithm is more subtle, but it is also relatively difficult to understand. We still take the above figure as an example to demonstrate its operation.

First, we build its adjacency matrix table, which is called Dmur1. In addition, we construct a matrix Pmur1, which is assigned as follows:

The superscript-1 indicates the initialization state, and each value in Pmur1 represents the intermediate point that needs to be passed from the vertex vi to the vertex vj. The default value indicates a direct connection and there is no intermediate point.

Once the initialization is complete, you can proceed with the Freudian algorithm. First of all, let the paths between all vertices go through v0, for example, from v1-> v2 to v1-> v0-> v2. It is found that the distance between v1-> v2 is 3, and the distance becomes 6 after v1-> v0-> v2, so there is no need to update the data. Since v3-v8 is not adjacent to v0, it cannot make v0 become the middle point, so it does not need to be updated, so after this operation, the data has not changed, but the state of the matrix has changed, from Dmurl to D0P, as shown below:

Now, the path between each vertex passes through v1, and we can see that the distance of v0-> v2 is 5, while the distance of v0-> v1-> v2 is 4, which is shorter than the direct distance. In the same way, v0-> v3 could not be reached directly. After v1, the path v0-> v1-> v3 distance becomes 8-> v1-> v4 distance becomes 6. With v2 as the starting point, the path v2-> v1-> v3 distance to v3 becomes 10. With v3 as the starting point, the distance to v0 and v2, and with v4 as the starting point, the distance to v0 has changed. At this point, because v1 is used as the intermediate point, part of the path is shortened, so the values of the two tables are updated as follows:

Some values of P are updated to 1, indicating that you need to pass through vertex v1 from vi to vj.

On this basis, we use the path between each vertex to go through v2 and do the same calculation again. The first data we find that need to be updated is v0-> v4, its distance is 6, and the distance of v0-> v2-> v4 is 5. So the value of D [0] [4] is updated to the value of P [0] [4] to the value of P [0] [2], because it is possible to pass through other intermediate points from v0-> v2. For example, this is through v1, so we change the path of v0-> v4 from the original v0->.-> v4 to from v0->.-> v2-> v4, as long as we keep iterating, we can find the complete path. The update results are as follows:

According to the same rules, we do the same thing with the rest of the data, and finally we get the result of the following figure:

Finally, each data of the D8 table represents the shortest distance from the vertex vi to the vertex vj, while each data of the P8 table represents the first intermediate vertex from the vertex vi to the vertex vj. For example, from v0-> v8, you first need to go through vertex v1, the full path is v0-> v1 plus v1-> v8, and v1-> v8 needs to go through v2, so the complete path is v0-> v1-> v2 plus v2-> v8, and the final shortest path is v0-> v1-> v2-> v4-> v3-> v6-> v7-> v8:

As you can see, the results are consistent with those using the Dijstra algorithm.

Code implements the Dijstra algorithm public void dijkstra (AMGraph amGraph, int fromIndex) {int len = amGraph.getVertexNum (); / / stores the shortest path subscript int [] p = new int [len] from fromIndex to other vertices; / / stores the weight of the shortest path from fromIndex to other vertices and int [] d = new int [len] / / Mark to find the shortest path from vertex fromIndex to other points boolean [] finded = new boolean [len]; / / initialize data for (int toIndex = 0; toIndex)

< len; toIndex++) { finded[toIndex] = false; d[toIndex] = amGraph.getWeight(fromIndex, toIndex); p[toIndex] = 0; } // fromIndex到自己的路径长度为0，并且不需要再求它的最短路径了 d[fromIndex] = 0; finded[fromIndex] = true; int min = 0; int k = -1; // 求fromIndex到toIndex的最短路径 for (int toIndex = 1; toIndex < len; toIndex++) { min = Integer.MAX_VALUE; // 寻找距离fromIndex最近的顶点 for (int i = 0; i < len; i++) { if (!finded[i] && d[i] < min) { // i 离 fromIndex最近 k = i; min = d[i]; } } // 找到了最近的点 finded[k] = true; // 更新剩余顶点的距离值 for (int i = 0; i < len; i++) { // 如果经过 k 之后的距离比直接到 i 的距离近，就更新距离 if (!finded[i] && amGraph.getWeight(k, i) != Integer.MAX_VALUE && (min + amGraph.getWeight(k, i) < d[i])) { d[i] = min + amGraph.getWeight(k, i); p[i] = k; } } System.out.println(); for (int i = 0; i < len; i++) { System.out.print(p[i] + "\t"); } }} 迪杰斯特拉算法的时间复杂度为O(n2)，但是它每次只能计算出从某一个顶点开始到其它顶点的最短路径。 弗洛伊德算法public void floyd(AMGraph amGraph) { int len = amGraph.getVertexNum(); int[][] d = new int[len][len]; int[][] p = new int[len][len]; // 初始化d和p数组 for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { d[i][j] = amGraph.getWeight(i, j); p[i][j] = j; } } for (int k = 0; k < len; k++) { for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { if (d[i][k] != Integer.MAX_VALUE && d[k][j] != Integer.MAX_VALUE && d[i][j] >

D [I] [k] + d [k] [j]) {d [I] [j] = d [I] [k] + d [k] [j]; p [I] [j] = p [I] [k];}} printD (len, d); printP (len, p);}

The Freudian algorithm is very elegant and concise, and can get the shortest path between any vertices, but because of the three-layer loop, its time complexity is O (n3).

Please refer to ShortestPath.java for the above code.

At this point, I believe you have a deeper understanding of the "example introduction of java Freud algorithm and Dijstra algorithm". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.