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

Editor to share with you how Java uses Dijkstra and Floyd to find the shortest path to the map, I believe most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!

1 Overview of the shortest path

In life, graphic structure is the most widely used. For example, in the common choice of traffic routes, the station can be regarded as the vertex, and if there is a path between the stations, it can be counted as the edge or arc between the two points, and the travel time between the stations can be regarded as the weight of the edge or arc.

The picture above is an example of how the choice of travel routes in life is mapped to the graphic structure. As a site, the vertex has the edge if it can be reached, and the travel time between the sites is the weight of the edge.

For the choice of travel route, different people have different choices. One of the most common options is to require the shortest total travel time between the departure and destination, regardless of how many stops there are. After all, travel time is precious to many people!

The transformation of such a problem into a mathematical model is to find the shortest path of the weighted graph, that is, to find the path with the least weight between the two vertices of the weighted graph. That is, if there may be more than one path from one vertex (source point) to another vertex (end point) in the graph, how to find a path to minimize the sum of weights (called path length) of the edges along the path.

In fact, the shortest path has two meanings: one has the least number of paths between two vertices, and the other is the shortest path distance between two vertices. This time, it mainly solves the problem of the shortest path distance, that is, the minimum weight sum. There are generally two common solving algorithms, Dijkstra algorithm and Floyd algorithm.

2. The principle of Dijkstra algorithm 2.1

Dijkstra algorithm was proposed by Dutch computer scientist Dick Stella in 1959, so it is also called Dixistra algorithm. It is the shortest path algorithm from one vertex to the other vertices, which solves the problem of finding the shortest path between specified vertices in a given weighted graph.

The Dijkstra algorithm does not find the shortest path from the starting point to the end point at once, but uses the greedy algorithm strategy to find the shortest path of the vertices between them step by step. In the process, based on the shortest path that has been obtained, the shortest path of the farther vertex is obtained, and finally the shortest path of the starting point and the end point is obtained.

The general steps are as follows:

1. Specify two sets S and U. The function of S is to record the vertices of the shortest path, while U is to record the vertices that have not yet found the shortest path, and the weight of these vertices to the starting vertex.

two。 Specify a starting vertex A, store it in set S, store other vertices and weights to vertex An in set U, find and remove the vertex B with the shortest path from U, and add it to S, and update the corresponding path weight in U (update the distance from the new node to the other nodes as an intermediate node) Repeat this until you traverse all the vertices, where the set in S is the shortest path from start A to the other vertices.

Dijstra algorithm only supports non-negative weight graphs, it calculates the shortest path from a single source to the remaining nodes, the time complexity is O (n ²), and runs faster for sparse graphs. If you want to know the shortest path from all vertices to all vertices, it is equivalent to another loop on the basis of the original algorithm, and the time complexity of the whole algorithm is O (n ³).

2.2 case study

This case corresponds to the case in the following implementation code, setting the starting point to A, initializing an array of paths from A to other points {0,99,8,2,99,3,99}, and initializing an array of flag bits {true, false, false}.

Start the first cycle, exclude the found path, that is, exclude 0, find the shortest path to A, find AmurD, that is, the vertex with index 3, set the shortest path flag bit of the corresponding position to true, and update the shortest path of the vertex that does not get the shortest path, because the shortest path of other found vertices has been found, here only needs to update the shortest path from the newly found D vertex path to point A. If the path through point D is smaller than the shortest path that already exists in the array, update the value.

Here the D point can reach C, B, M, C, B, / / continue queuing indexLinkedList.add (k);} System.out.println () } / * returns the index of the first adjacent vertex of vertex v. If it fails, it returns the index of-1 * * @ param v vertex v in the array * @ return returns the index of the first adjacent vertex of vertex v, or returns-1 * / private int firstVertex (int v) {/ / if the index is out of range,-1 if (v)

< 0 || v >

(vertexs.length-1)) {return-1;} / * according to the law of the adjacency matrix: the vertex index v corresponds to the matrix [v] [I] row record of the edge two-dimensional matrix * starting with iS0 * / for (int iS0; I)

< vertexs.length; i++) { if (matrix[v][i] != 0 && matrix[v][i] != NO_EDGE) { return i; } } return -1; } /** * 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1 * * @param v 顶点索引 * @param w 第一个邻接点索引 * @return 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1 */ private int nextVertex(int v, int w) { //如果索引超出范围,则返回-1 if (v < 0 || v >

(vertexs.length-1) | | w

< 0 || w >

(vertexs.length-1)) {return-1;} / * according to the law of the adjacency matrix: the vertex index v corresponds to the matrix [v] [I] row record of the edge two-dimensional matrix * since the index of the adjacency point w has been obtained, we start looking for * / for (int i=w+1; I) from i=w+1.

< vertexs.length; i++) { if (matrix[v][i] != 0 && matrix[v][i] != NO_EDGE) { return i; } } return -1; } /** * 输出图 * * @return 输出图字符串 */ @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); for (int i = 0; i < vertexs.length; i++) { for (int j = 0; j < vertexs.length; j++) { stringBuilder.append(matrix[i][j]).append("\t"); } stringBuilder.append("\n"); } return stringBuilder.toString(); } /** * Prim算法求最小生成树 */ public void prim() { System.out.println("prim: "); //对应节点应该被连接的前驱节点,用来输出 //默认为0,即前驱结点为第一个节点 int[] mid = new int[matrix.length]; //如果某顶点作为末端顶点被连接，对应位置应该为true //第一个顶点默认被连接 boolean[] connected = new boolean[matrix.length]; connected[0] = true; //存储未连接顶点到已连接顶点的最短距离(最小权) int[] dis = new int[matrix.length]; //首先将矩阵第一行即其他顶点到0索引顶点的权值拷贝进去 System.arraycopy(matrix[0], 0, dis, 0, matrix.length); //存储路径长度 int sum = 0; //最小权值 int min; /*默认第一个顶点已经找到了,因此最多还要需要大循环n-1次*/ for (int k = 1; k < matrix.length; k++) { min = NO_EDGE; //最小权值的顶点的索引 int minIndex = 0; /*寻找权值最小的且未被连接的顶点索引*/ for (int i = 1; i < matrix.length; i++) { //排除已连接的顶点,排除权值等于0的值,这里权值等于0表示已生成的最小生成树的顶点都未能与该顶点连接 if (!connected[i] && dis[i] != 0 && dis[i] < min) { min = dis[i]; minIndex = i; } } //如果没找到,那么该图可能不是连通图,直接返回了,此时最小生成树没啥意义 if (minIndex == 0) { return; } //权值和增加 sum += min; //该新连接顶点对应的索引值变成true,表示已被连接,后续判断时跳过该顶点 connected[minIndex] = true; //输出对应的前驱顶点到该最小顶点的权值 System.out.println("\t" + vertexs[mid[minIndex]] + " --->

"+ vertexs [minIndex] +" weight: "+ min); / * the minimum weights of all other vertices to connected vertices before the new vertex minIndex is added have been calculated, so you only need to update other unconnected vertices to see if minIndex has shorter weights, and if so, update to find the vertex with the least weight from the connected vertex * / for (int I = 1; I).

< matrix.length; i++) { //如果该顶点未连接 if (!connected[i]) { /*如果新顶点到未连接顶点i的权值不为0,并且比原始顶点到未连接顶点i的权值还要小,那么更新对应位置的最小权值*/ if (matrix[minIndex][i] != 0 && dis[i] >

Matrix [minIndex] [I]) {/ / update the minimum weight dis [I] = matrix [minIndex] [I]; / / update the precursor node index as the newly added node index mid [I] = minIndex } System.out.println ("\ t" + "sum:" + sum);} / * Kruskal algorithm is traditionally implemented to find the minimum spanning tree, which requires knowing the edge set array and vertex array * / public void kruskal () {System.out.println ("Kruskal:") / / since the edge set array is saved when creating the graph, you can just use / / Edge [] edges= getEdges (); / / this.edges=edges; / / sort the edge set array with a pair of Arrays.sort (this.edges, Comparator.comparingInt (o-> o.weight)) / / the index int [] vends = new int [this.edges.length] used to hold the final end point of each vertex in the existing minimum spanning tree; / / it is possible to know that the end point index range is [0dthis.edges.endthway1], so filling edges.length means there is no destination Arrays.fill (vends, this.edges.length); int sum = 0 For (Edge edge: this.edges) {/ / get the start index from int from = getPosition (edge.from) of the I edge; / / get the end index to int to = getPosition (edge.to) of the I edge; / / get the end point int m = getEndIndex (vends, from) of the vertex from in the "minimum spanning tree available" / / get the end point of vertex to in the "existing minimum spanning tree" int n = getEndIndex (vends, to) / / if no loop is formed, it can be added, otherwise it can be skipped directly, and the next edge will be judged by if (masking n) {/ / add the original end point index m to n vends [m] = n in the existing minimum spanning tree. System.out.println ("\ t" + vertexs [from] + "-->" + vertexs [to] + "weight:" + edge.weight); sum + = edge.weight;}} System.out.println ("\ t" + "sum:" + sum); / / System.out.println (Arrays.toString (this.edges)) } / * get the end point of vertex index I if there is no end point, return vertex index itself * * @ param vends vertex index in the minimum spanning tree * @ param I vertex index * @ return vertex index I end point if there is no end point return vertex index itself * / private int getEndIndex (int [] vends) Int I) {/ / the logic of circular search is used here to find the final destination while (vends [I]! = this.edges.length) {I = vends [I] } return I;} / * if there is no ready-made edge set array, then obtain the edge set array of the graph * * @ return graph according to the adjacency matrix structure * / private Edge [] getEdges () {List edges = new ArrayList () / * traversing the matrix array requires only half of the traversal * / for (int I = 0; I)

< vertexs.length; i++) { for (int j = i + 1; j < vertexs.length; j++) { //如果存在边 if (matrix[i][j] != NO_EDGE && matrix[i][j] != 0) { edges.add(new Edge(vertexs[i], vertexs[j], matrix[i][j])); //edges[index++] = new Edge(vertexs[i], vertexs[j], matrix[i][j]); } } } return edges.toArray(new Edge[0]); } /** * Kruskal结合Prim算法.不需要知道边集,只需要矩阵数组,和顶点数组 * 同样是求最小权值的边,但是有一个默认起点顶点,该起点可以是要求[0,顶点数量-1]之间的任意值，同时查找最小权的边。 * 可能会有Bug,目前未发现 */ public void kruskalAndPrim() { System.out.println("kruskalAndPrim: "); //已经找到的边携带的顶点对应的索引将变为true,其余未找到边对应的顶点将是false boolean[] connected = new boolean[matrix.length]; //这里选择第一个顶点为起点,表示以该顶点开始寻找包含该顶点的最小边 connected[0] = true; int sum = 0, n1 = 0, n2 = 0; //最小权值 int min; while (true) { min = NO_EDGE; /*找出所有带有已找到顶点的边中,最小权值的边,只需要寻找对称矩阵的一半即可*/ //第一维 for (int i = 0; i < matrix.length; i++) { //第二维 for (int j = i + 1; j < matrix.length; j++) { //排除等于0的,排除两个顶点都找到了的,这里实际上已经隐含了排除环的逻辑,如果某条边的两个顶点都找到了,那么如果算上该条边,肯定会形成环 //寻找剩下的最小的权值的边 if (matrix[i][j] != 0 && connected[i] != connected[j] && matrix[i][j] < min) { min = matrix[i][j]; n1 = i; n2 = j; } } } //如果没找到最小权值,该图可能不是连通图,或者已经寻找完毕,直接返回 if (min == NO_EDGE) { System.out.println("\t" + "sum:" + sum); return; } //已经找到的边对应的两个顶点都置为true connected[n1] = true; connected[n2] = true; //输出找到的边和最小权值 System.out.println("\t" + vertexs[n1] + " --->

"+ vertexs [N2] +" weight: "+ min); sum + = min;}} / * Dijkstra algorithm to find the shortest path. * * @ param start starting vertex index. That is, the shortest path from "vertex vs" to other vertices is calculated. * / public void dijkstra (int start) {checkIndex (start); int [] shortestPathance = getShortestDistance (start, vertexs.length); / / print the result of the shortest path to Dijkstra System.out.println ("Dijkstra (" + vertexs [start] + "):"); for (int I = 0; I

< vertexs.length; i++) { System.out.println("\t(" + vertexs[start] + " --->

"+ vertexs [I] +") shortest path: "+ shortestPathance [I]) }} / * Dijkstra algorithm to find the shortest path * * @ param start starting point * @ param end end point, if the end=vertexs.length description is to traverse to find all the shortest paths * @ return starting vertex to another point or the shortest weight of the specified point * / private int [] getShortestDistance (int start Int end) {/ * 1, the array stores the weight of the starting vertex to other points * / int [] shortestPathance = new int [vertexs.length] / / initialize the data / / first set the shortest path from the starting point to the vertex I as the weight from the starting point to the vertex I. System.arraycopy (matrix [start], 0, shortestPathance, 0, matrix.length); / * 2, flag bit array. A position if true indicates that the shortest path from the vertex of the corresponding position to the starting vertex has been successfully obtained. * / boolean [] shortest = new boolean [vertexs.length]; / / the path from the starting point to itself has been found, which is 0 shortest [start] = true; / * 3, traversing the vertexs.length-1 at most, and finding the shortest path from the starting point to one vertex each time. * / int k; int min; for (int I = 1; I

< vertexs.length; i++) { k = 0; // 寻找当前最小的路径； min = NO_EDGE; for (int j = 0; j < vertexs.length; j++) { //排除已经找到的最短路径之后，找到离start最近的顶点(k)。 if (!shortest[j] && shortestPathance[j] < min) { min = shortestPathance[j]; k = j; } } //先设置起始点到新顶点k的最短路径已经找到 shortest[k] = true; if (end != vertexs.length && k == end) { break; } //更新未获取最短路径的顶点的最短路径,因为其他已找到的顶点的最短路径已经找到了,这里指需要更新新加入的已找到的可达顶点的路径. for (int j = 0; j < vertexs.length; j++) { int tmp = matrix[k][j]; //排除已经找到的最短路径，排除未连接的路径，排除等于0的路径（连接自己）之后 //找到离start最如果新的最短路径比以前的最短路径还要短，则更新最短路径。 if (!shortest[j] && tmp != NO_EDGE && tmp != 0 && ((tmp = min + tmp) < shortestPathance[j])) { shortestPathance[j] = tmp; } } } return shortestPathance; } /** * 索引检查 * * @param index 多个索引 */ private void checkIndex(int... index) { for (int i : index) { if (i < 0 || i >

= vertexs.length) {throw new ArrayIndexOutOfBoundsException ("Index out of bounds:" + I);}} / * Dijkstra algorithm to find the shortest path. * * @ param start starting vertex index. * @ param end end point index * / public void dijkstra (int start, int end) {checkIndex (start, end); int [] shortestPathance = getShortestDistance (start, end); / / print the result of the Dijkstra shortest path System.out.println ("Dijkstra (" + vertexs [start] + "-->" + vertexs [end] + ") shortest path:" + shortestPathance [end]) } / * Floyd algorithm to obtain the shortest path from all vertices to all vertices, the code is very simple, the idea is very clever * / public void floyd () {/ / path matrix (the shortest path between two vertices, that is, the minimum weight) int [] [] shortestPath = new int [matrix.length] [matrix.length]; / * initialize data * / for (int I = 0; I)

< matrix.length; i++) { System.arraycopy(matrix[i], 0, shortestPath[i], 0, vertexs.length); } // 计算最短路径 for (int k = 0; k < matrix.length; k++) { for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix.length; j++) { //要求经过下标k顶点的两个路径都不能等于NO_EDGE,否则就是没有路径,NO_EDGE应该选取的足够的大,否则可能出错 int tmp = (shortestPath[i][k] == NO_EDGE || shortestPath[k][j] == NO_EDGE) ? NO_EDGE : (shortestPath[i][k] + shortestPath[k][j]); // 如果经过下标为k顶点路径比原两点间路径更短，则更新shortestPath[i][j] if (shortestPath[i][j] >

Tmp) the value corresponding to the shortest path from / / I to j is set to a smaller shortestPath [I] [j] = tmp;} / * output path matrix * / System.out.println ("Floyd:") through k For (int I = 0; I

< matrix.length; i++) { for (int j = 0; j < matrix.length; j++) { System.out.print("\t" + shortestPath[i][j]); } System.out.println(); } } public static void main(String[] args) { //顶点数组 Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; //边数组,加权值 Edge[] edges = { new Edge('A', 'C', 8), new Edge('D', 'A', 2), new Edge('A', 'F', 3), new Edge('B', 'C', 4), new Edge('C', 'D', 5), new Edge('E', 'G', 6), new Edge('E', 'B', 7), new Edge('D', 'B', 9), new Edge('F', 'G', 9)}; //构建图 MatrixDijkstraAndFloyd matrixDijkstraAndFloyd = new MatrixDijkstraAndFloyd(vexs, edges); //输出图 System.out.println(matrixDijkstraAndFloyd); //深度优先遍历 matrixDijkstraAndFloyd.DFS(); //广度优先遍历 matrixDijkstraAndFloyd.BFS(); //Prim算法输出最小生成树 matrixDijkstraAndFloyd.prim(); //Kruskal算法输出最小生成树 matrixDijkstraAndFloyd.kruskal(); //Kruskal算法结合Prim算法输出最小生成树,可能会有Bug,目前未发现 matrixDijkstraAndFloyd.kruskalAndPrim(); // Dijkstra算法获取某个索引的顶点到其它各个顶点的最短距离 // 这里参数是索引,也可以是一个顶点,需要稍微修改代码获取顶点的索引,比较简单这里就不做了 matrixDijkstraAndFloyd.dijkstra(0); // Dijkstra算法获取一个顶点到另一个顶点的最短距离 matrixDijkstraAndFloyd.dijkstra(2, 0); // Floyd算法获取所有顶点到所有顶点的最短路径 matrixDijkstraAndFloyd.floyd(); }}5 邻接表加权图实现 这里的实现能够构造一个基于邻接表实现无向加权图的类；并且提供深度优先遍历和广度优先遍历的方法，提供获取边集数组的方法，提供Prim和Kruskal两种求最小生成树的方法，提供Dijkstra和Floyd两种求最短路径的方法。 /** * 无向加权图邻接表实现 * {@link ListDijkstraAndFloyd#ListDijkstraAndFloyd(Object[], Edge[])} 构建无向加权图 * {@link ListDijkstraAndFloyd#DFS()} 深度优先遍历无向加权图 * {@link ListDijkstraAndFloyd#BFS()} 广度优先遍历无向加权图 * {@link ListDijkstraAndFloyd#toString()} 输出无向加权图 * {@link ListDijkstraAndFloyd#prim()} Prim算法实现最小生成树 * {@link ListDijkstraAndFloyd#kruskal()} Kruskal算法实现最小生成树 * {@link ListDijkstraAndFloyd#getEdges()} 获取边集数组 * {@link ListDijkstraAndFloyd#dijkstra(int)} ()} 获取指定顶点到所有顶点的最短路径 * {@link ListDijkstraAndFloyd#dijkstra(int, int)} 获取指定顶点到指定顶点的最短路径 * {@link ListDijkstraAndFloyd#floyd()} Floyd获取所有顶点到所有顶点的最短路径 * * @author lx */public class ListDijkstraAndFloyd { /** * 顶点类 * * @param */ private class Node { /** * 顶点信息 */ E data; /** * 指向第一条依附该顶点的边 */ LNode firstLNode; public Node(E data, LNode firstLNode) { this.data = data; this.firstLNode = firstLNode; } } /** * 边表节点类 */ private class LNode { /** * 该边所指向的顶点的索引位置 */ int vertex; /** * 该边的权值 */ int weight; /** * 指向下一条边的指针 */ LNode nextLNode; } /** * 边对象,具有权值,在构建加权无向图时使用 */ private static class Edge { private E from; private E to; private int weight; public Edge(E from, E to, int weight) { this.from = from; this.to = to; this.weight = weight; } @Override public String toString() { return "Edge{" + "from=" + from + ", to=" + to + ", weight=" + weight + '}'; } } /** * 顶点数组 */ private Node[] vertexs; /** * 边数组 */ private Edge[] edges; /** * 由于是加权图,这里设置一个边的权值上限,任何边的最大权值不能大于等于该值，在实际应用中，该值应该根据实际情况确定 */ private static final int NO_EDGE = 99; /** * 创建无向加权图 * * @param vexs 顶点数组 * @param edges 边二维数组 */ public ListDijkstraAndFloyd(E[] vexs, Edge[] edges) { this.edges = edges; /*初始化顶点数组,并添加顶点*/ vertexs = new Node[vexs.length]; for (int i = 0; i < vertexs.length; i++) { vertexs[i] = new Node(vexs[i], null); } /*初始化边表,并添加边节点到边表尾部,即采用尾插法*/ for (Edge edge : edges) { // 读取一条边的起始顶点和结束顶点索引值 int p1 = getPosition(edge.from); int p2 = getPosition(edge.to); int weight = edge.weight; /*这里需要相互添加边节点,无向图可以看作相互可达的有向图*/ // 初始化lnode1边节点 LNode lnode1 = new LNode(); lnode1.vertex = p2; lnode1.weight = weight; // 将LNode链接到"p1所在链表的末尾" if (vertexs[p1].firstLNode == null) { vertexs[p1].firstLNode = lnode1; } else { linkLast(vertexs[p1].firstLNode, lnode1); } // 初始化lnode2边节点 LNode lnode2 = new LNode(); lnode2.vertex = p1; lnode2.weight = weight; // 将lnode2链接到"p2所在链表的末尾" if (vertexs[p2].firstLNode == null) { vertexs[p2].firstLNode = lnode2; } else { linkLast(vertexs[p2].firstLNode, lnode2); } } } /** * 获取某条边的某个顶点所在顶点数组的索引位置 * * @param e 顶点的值 * @return 所在顶点数组的索引位置, 或者-1 - 表示不存在 */ private int getPosition(E e) { for (int i = 0; i < vertexs.length; i++) { if (vertexs[i].data == e) { return i; } } return -1; } /** * 将lnode节点链接到边表的最后,采用尾插法 * * @param first 边表头结点 * @param node 将要添加的节点 */ private void linkLast(LNode first, LNode node) { while (true) { if (first.vertex == node.vertex) { return; } if (first.nextLNode == null) { break; } first = first.nextLNode; } first.nextLNode = node; } @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); for (int i = 0; i < vertexs.length; i++) { stringBuilder.append(i).append("(").append(vertexs[i].data).append("): "); LNode node = vertexs[i].firstLNode; while (node != null) { stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append("-").append(node.weight).append(")"); node = node.nextLNode; if (node != null) { stringBuilder.append("->

");} else {break;}} stringBuilder.append ("\ n ");} return stringBuilder.toString () } / * * the recursive implementation of the depth-first search traversal graph is similar to the preorder traversal of the tree * so it simulates the preorder traversal of the tree and also borrows the stack structure, which is the recursion of the method, the implicit borrowing stack * * @ param I vertex index * @ param visited access flag array * / private void DFS (int I) Boolean [] visited) {/ / Index is marked as true, indicating that visited [I] = true has been accessed System.out.print (vertexs [I] .data + "); / / get the vertex's edge header node LNode node = vertexs [I] .firstLNode; / / cycle through the vertex's adjacent points, and recursively search for while (node! = null) {if (! visited [node.vertex]) {DFS (node.vertex, visited) in the same way } node = node.nextLNode;}} / * depth first search traversal graph, similar to the preorder traversal of the tree, * / public void DFS () {/ / create a new vertex access tag array, corresponding to each index corresponding to the vertex array of vertices in the same index boolean [] visited = new boolean [vertexs.length] / / initialize all vertices without access to for (int I = 0; I

< vertexs.length; i++) { visited[i] = false; } System.out.println("DFS: "); System.out.print("\t"); /*循环搜索*/ for (int i = 0; i < vertexs.length; i++) { //如果对应索引的顶点的访问标记为false,则搜索该顶点 if (!visited[i]) { DFS(i, visited); } } /*走到这一步,说明顶点访问标记数组全部为true,说明全部都访问到了,深度搜索结束*/ System.out.println(); } /** * 广度优先搜索图,类似于树的层序遍历 * 因此模仿树的层序遍历,同样借用队列结构 */ public void BFS() { // 辅组队列 Queue indexLinkedList = new LinkedList(); //新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点 boolean[] visited = new boolean[vertexs.length]; //初始化所有顶点都没有被访问 for (int i = 0; i < vertexs.length; i++) { visited[i] = false; } System.out.println("BFS: "); System.out.print("\t"); for (int i = 0; i < vertexs.length; i++) { //如果访问方剂为false,则设置为true,表示已经访问,然后开始访问 if (!visited[i]) { visited[i] = true; System.out.print(vertexs[i].data + " "); indexLinkedList.add(i); } //判断队列是否有值,有就开始遍历 if (!indexLinkedList.isEmpty()) { //出队列 Integer j = indexLinkedList.poll(); LNode node = vertexs[j].firstLNode; while (node != null) { int k = node.vertex; if (!visited[k]) { visited[k] = true; System.out.print(vertexs[k].data + " "); //继续入队列 indexLinkedList.add(k); } node = node.nextLNode; } } } System.out.println(); } /** * Prim算法求最小生成树 */ public void prim() { System.out.println("prim: "); //对应节点应该被连接的前驱节点,用来输出 //默认为0,即前驱结点为第一个节点 int[] mid = new int[vertexs.length]; int start = 0; int min, tmp, sum = 0; int num = vertexs.length; //顶点间边的权值 //存储未连接顶点到已连接顶点的最短距离(最小权) int[] dis = new int[num]; // 初始化"顶点的权值数组"， // 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。 //首先将其他顶点到0索引顶点的权值存储进去 for (int i = 0; i < num; i++) { dis[i] = getWeight(start, i); } //如果某顶点作为末端顶点被连接，对应位置应该为true //第一个顶点默认被连接 boolean[] connected = new boolean[vertexs.length]; connected[0] = true; /*默认第一个顶点已经找到了,因此最多还要需要大循环n-1次*/ for (int k = 1; k < num; k++) { min = NO_EDGE; //最小权值的顶点的索引 int minIndex = 0; // 在未被加入到最小生成树的顶点中，找出权值最小的顶点。 for (int i = 1; i < vertexs.length; i++) { //排除已连接的顶点,排除权值等于0的值,因为这里默认顶点指向自己的权值为0 if (!connected[i] && dis[i] != 0 && dis[i] < min) { min = dis[i]; minIndex = i; } } //如果没找到,那么该图可能不是连通图,直接返回了,此时最小生成树没啥意义 if (minIndex == 0) { return; } //权值和增加 sum += min; //该新连接顶点对应的索引值变成true,表示已被连接,后续判断时跳过该顶点 connected[minIndex] = true; //输出对应的前驱顶点到该最小顶点的权值 System.out.println("\t" + vertexs[mid[minIndex]].data + " --->

"+ vertexs [minIndex] .data +" weight: "+ min); / * the minimum weight of all other vertices to the connected vertex before the new vertex minIndex is added has been calculated, so you only need to update the other vertices to see if there are shorter weights for the newly connected vertex minIndex, and if so, update to find the vertex with the least weight from the connected vertex * / for (int I = 1; I)

< num; i++) { //如果该顶点未连接 if (!connected[i]) { // 获取minindex顶点到未连接顶点i的权值 tmp = getWeight(minIndex, i); /*如果新顶点到未连接顶点i的权值不为0,并且比原始顶点到未连接顶点i的权值还要小,那么更新对应位置的最小权值*/ if (tmp != 0 && dis[i] >

Tmp) {dis [I] = tmp; / / Update the precursor node index mid [I] = minIndex;} System.out.println ("\ t" + "sum:" + sum) } / * try to get the weight of the edge from the beginning of the edge start to the end of the edge end, of course, you may not get the weight of * * @ param start edge start * @ param end edge end * @ return; if the start point and the end point are the same, return 0 If there is no edge between the beginning and end of the edge, return NO_EDGE * / private int getWeight (int start, int end) {/ / if start=end, then return 0 if (start= = end) {return 0;} / / get the first value of the edge table of the vertex LNode node = vertexs [start] .firstLNode / / Loop to find the edge table to see if you can find the corresponding index = end. If you can't find it, return NO_EDGE, indicating that the two vertices are not connected. While (node! = null) {if (end = = node.vertex) {return node.weight;} node = node.nextLNode;} return NO_EDGE } / * Kruskal algorithm to find the minimum spanning tree, it can be said that the adjacency matrix and the adjacency list are implemented in the same way * / public void kruskal () {System.out.println ("Kruskal:"); / / since the edge set array is saved when creating the graph, it can be used directly here / / Edge [] edges= getEdges (); / / this.edges=edges / / an array of edge sets is sorted Arrays.sort (this.edges, Comparator.comparingInt (o-> o.weight)); / / the index int [] vends = new int [this.edges.length] used to hold the final end point of each vertex in the existing minimum spanning tree / / it is possible to know that the end index range is [0herothis.edges.futhmer1], so filling edges.length means there is no end point Arrays.fill (vends, this.edges.length); int sum = 0; for (Edge edge: this.edges) {/ / get the starting index from int from = getPosition (edge.from) of the first edge. / / get the end point index of edge I to int to = getPosition (edge.to); / / get the end point of vertex from in "existing minimum spanning tree" int m = getEndIndex (vends, from); / / get the end point of vertex to in "existing minimum spanning tree" int n = getEndIndex (vends, to) / / if no loop is formed, it can be added, otherwise it can be skipped directly, and the next edge will be judged by if (masking n) {/ / add the original end point index m to n vends [m] = n in the existing minimum spanning tree. System.out.println ("\ t" + vertexs [from] .data + "-->" + vertexs [to] .data + "weight:" + edge.weight); sum + = edge.weight;}} System.out.println ("\ t" + "sum:" + sum); / / System.out.println (Arrays.toString (this.edges)) } / * get the end point of vertex index I if there is no end point, return vertex index itself * * @ param vends vertex index in the minimum spanning tree * @ param I vertex index * @ return vertex index I end point if there is no end point return vertex index itself * / private int getEndIndex (int [] vends) Int I) {/ / the logic of circular search is used here to find the final destination while (vends [I]! = this.edges.length) {I = vends [I] } return I;} / * if there is no ready-made edge set array, then the edge set array of the graph * * @ return graph is obtained according to the adjacency table structure * / private Edge [] getEdges () {List edges = new ArrayList (); / / traversal vertex array for (int I = 0; I)

< vertexs.length; i++) { LNode node = vertexs[i].firstLNode; while (node != null) { //只需添加起点索引小于终点索引的边就行了 if (node.vertex >

I) {edges.add (new Edge (vertexs [I] .data, vertexs [node.vertex] .data, node.weight));} node = node.nextLNode;}} return edges.toArray (new Edge [0]);} / * Dijkstra algorithm to find the shortest path. * * @ param start starting vertex index. That is, the shortest path from "vertex vs" to other vertices is calculated. * / public void dijkstra (int start) {checkIndex (start); int [] distance = getShortestDistance (start, vertexs.length); / / print the result of the shortest path of dijkstra System.out.println ("dijkstra (" + vertexs [start] .data + "):"); for (int I = 0; I

< vertexs.length; i++) { System.out.println("\t(" + vertexs[start].data + " --->

"+ vertexs [I] .data +") shortest path: "+ distance [I]);}} / * Dijkstra algorithm to find the shortest path. * * @ param start starting vertex index. * @ param end end point index * / public void dijkstra (int start, int end) {checkIndex (start, end); int [] shortestPathance = getShortestDistance (start, end); / / print the result of the dijkstra shortest path System.out.println ("Dijkstra (" + vertexs [start] .data + "-->" + vertexs [end] .data + ") the shortest path:" + shortestPathance [end]) } / * Dijkstra algorithm to find the shortest path * * @ param start starting point * @ param end end point, if the end=vertexs.length description is to traverse to find all the shortest paths * @ return starting vertex to another point or the shortest weight value of the specified point * / private int [] getShortestDistance (int start Int end) {/ * 1, the array stores the weight of the starting vertex to other points * / int [] distance = new int [vertexs.length] / / initialization data for (int I = 0; I

< vertexs.length; i++) { //首先设置起始点到顶点i到的最短路径为起始点到顶点i的权。 distance[i] = getWeight(start, i); } /*2、标志位数组.某个位置表示true表示,对应位置的顶点到起始顶点的最短路径已成功获取。*/ boolean[] shortest = new boolean[vertexs.length]; //首先设置起始点到自己的的路径已经找到了,为0 shortest[start] = true; /*3、最多遍历vertexs.length-1次；每次找出起始点到一个顶点的最短路径。*/ int k; int min; for (int i = 1; i < vertexs.length; i++) { k = 0; // 寻找当前最小的路径； min = NO_EDGE; for (int j = 0; j < vertexs.length; j++) { //排除已经找到的最短路径之后，找到离start最近的顶点(k)。 if (!shortest[j] && distance[j] < min) { min = distance[j]; k = j; } } //先设置起始点到新顶点k的最短路径已经找到 shortest[k] = true; if (end != vertexs.length && k == end) { break; } //更新未获取最短路径的顶点的最短路径,因为其他已找到的顶点的最短路径已经找到了,这里指需要更新新加入的已找到的可达顶点的路径. for (int j = 0; j < vertexs.length; j++) { int tmp = getWeight(k, j); //排除已经找到的最短路径，排除未连接的路径，排除等于0的路径（连接自己）之后 //找到离start最如果新的最短路径比以前的最短路径还要短，则更新最短路径。 if (!shortest[j] && tmp != NO_EDGE && tmp != 0 && ((tmp = min + tmp) < distance[j])) { distance[j] = tmp; } } } return distance; } /** * 索引检查 * * @param index 多个索引 */ private void checkIndex(int... index) { for (int i : index) { if (i < 0 || i >

= vertexs.length) {throw new ArrayIndexOutOfBoundsException ("Index out of bounds:" + I) } / * Floyd algorithm obtains the shortest path from all vertices to all vertices, which is basically consistent with the implementation of adjacency matrix * / public void floyd () {/ / path matrix (two vertices shortest path, that is, minimum weight) int [] [] shortestPath = new int [vertexs.length] [vertexs.length] / * initialization data * / for (int I = 0; I

< vertexs.length; i++) { for (int j = 0; j < vertexs.length; j++) { //获取两点的直接权值 //如果是频繁调用该方法,因此可以创建一个属于对象的权值矩阵用来保存权值,这里为了简单没做 shortestPath[i][j] = getWeight(i, j); } } // 计算最短路径 for (int k = 0; k < vertexs.length; k++) { for (int i = 0; i < vertexs.length; i++) { for (int j = 0; j < vertexs.length; j++) { //要求经过下标k顶点的两个路径都不能等于NO_EDGE,否则就是没有路径,NO_EDGE应该选取的足够的大,否则可能出错 int tmp = (shortestPath[i][k] == NO_EDGE || shortestPath[k][j] == NO_EDGE) ? NO_EDGE : (shortestPath[i][k] + shortestPath[k][j]); // 如果经过下标为k顶点路径比原两点间路径更短，则更新shortestPath[i][j] if (shortestPath[i][j] >

Tmp) the value corresponding to the shortest path from / / I to j is set to a smaller shortestPath [I] [j] = tmp;} / * output path matrix * / System.out.println ("Floyd:") through k For (int I = 0; I < vertexs.length; iTunes +) {for (int j = 0; j < vertexs.length; jacks +) {System.out.print ("\ t" + shortestPath [I] [j]);} System.out.println () }} public static void main (String [] args) {/ / vertex array Character [] vexs = {'Agar,' baked, 'clocked,' dashed, 'eyed,' faded,'G'} / / Edge array, weighted values Edge [] edges = {new Edge ('A','C', 8), new Edge ('A','A', 2), new Edge ('A','C', 3), new Edge ('B,'C, 4), new Edge ('C') 'During, 5), new Edge ('estranged,' Globe, 6), new Edge ('estranged,' baked, 7), new Edge ('dashed,' baked, 9), new Edge ('favored,' Globe, 9)} / / build ListDijkstraAndFloyd listDijkstraAndFloyd = new ListDijkstraAndFloyd (vexs, edges); / / output diagram System.out.println (listDijkstraAndFloyd); / / depth-first traversal / / DFS: / / A C B E G F D listDijkstraAndFloyd.DFS (); / / breadth-first traversal / / BFS: / / A C DF B G E listDijkstraAndFloyd.BFS () / / Prim algorithm to find the minimum spanning tree listDijkstraAndFloyd.prim (); / / Kruskal algorithm to find the minimum spanning tree listDijkstraAndFloyd.kruskal () / / the Dijkstra algorithm obtains the shortest distance from the vertex of an index to the other vertices / / here the parameter is the index, or it can be a vertex. You need to modify the code to get the index of the vertex slightly, so it is simple not to do listDijkstraAndFloyd.dijkstra (0) here; / / the Dijkstra algorithm obtains the shortest distance listDijkstraAndFloyd.dijkstra (2,0) from one vertex to another vertex. / / Floyd algorithm to get the shortest path from all vertices to all vertices listDijkstraAndFloyd.floyd ();}} this is all the content of the article "how to use Dijkstra and Floyd to find the shortest path of a graph by Java". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

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.