This is the ninth day of my participation in the First Challenge 2022. For details: First Challenge 2022.
This paper introduces the concept of graph shortest path in detail, then introduces the principle of two algorithms: Dijkstra algorithm and Floyd algorithm to find the shortest path, and finally provides the Java implementation of graph pair algorithm based on adjacency matrix and adjacency list.
To read this article, you need to have a basic knowledge of diagrams. If you are not familiar with diagrams, you can check out this article: Introduction to diagram concepts and storage structures, traversal methods and Java code implementation.
1 Overview of shortest paths
In life, graphic structure is the most widely used. For example, for common traffic route selection, stations can be regarded as vertices, and if there is a path between stations, it can be counted as the edge or arc between two points, and the passage time between stations can be regarded as the weight of the edge or arc.
The picture above is an example of how the choice of travel route is mapped to a graphic structure in life. The vertex serves as the site, and if the sites can reach each other, they have an edge, and the passage time between the sites is the weight of the edge.
As for the choice of travel route, different people have different choices. One common option is to require the shortest total travel time between the origin and destination, regardless of the number of stops. After all, travel time is precious to many people!
This problem is transformed into a mathematical model, is to find the shortest path of the weighted graph, is to find the path of the lowest 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 (destination point) in the graph, how to find a path that minimizes the sum of weights (called path length) of all edges along this path.
In fact, the shortest path has two meanings, one is the least number of paths between two vertices, the other is the shortest path distance between two vertices, this time mainly to solve the shortest path distance problem, that is, the minimum weight and. The common solution algorithm is generally two kinds, Dijkstra algorithm and Floyd algorithm.
2 Dijkstra algorithm
2.1 the principle
Dijkstra algorithm was put forward by Dutch computer scientist Dijkstra in 1959, so it is also called Dijkstra algorithm. The shortest path algorithm from one vertex to other vertices solves the problem of finding the shortest path between specified vertices in a given weighted graph
Dijkstra algorithm is not immediately find out the starting point to the end of the shortest path, but is the greedy algorithm strategy, step by step to find the vertices of the shortest path between them, are based on has been calculated in the process of the shortest path, on the basis of obtained further vertices of the shortest path, eventually get the starting point and end point of the shortest path.
The general steps are as follows:
- Specify two sets S and U. The purpose of S is to record the vertices of the shortest path that have been found, and U is to record the vertices of the shortest path that have not been found, and the weights of those vertices to the starting vertex.
- Specify A starting vertices A, in the set S, other vertex and to the vertices of A right in the set U, to find and remove the shortest path from U vertex B, and join the S, and update the path of the corresponding weights in the U (updated source will be new node as the distance of intermediate nodes to other nodes). Repeat this operation until all vertices have been traversed, at which point the set in S is the shortest path from starting point A to each of the other vertices.
Dijkstra algorithm only supports non-negative weighted graphs. It calculates single-source shortest paths, that is, the shortest paths from a single source point to the remaining nodes. The time complexity is O(n²), and it runs faster for sparse graphs. If I want to know the shortest path from all vertices to all vertices, then I’m going to loop through the algorithm again, and the time of the whole algorithm becomes O(n^3^).
2.2 Case Analysis
This case corresponds to the case in the implementation code below, set the starting point as A, initialize the array of paths from A to other points {0, 99, 8, 2, 99, 3, 99}, initialize the array of flag bits {true, false, false, false, false, false}.
Started in the first round of circulation, eliminate has found A path, namely the exclusion of 0, to find A shortest path, found A – D, the index of three vertices, set up corresponding location marker of the shortest path to true, the update did not obtain the shortest path of the vertices of the shortest path, because the other has found the vertices of the shortest path has been found, Here you just update the shortest path from the newly found vertex path reachable by D to point A, and if the path through point D is smaller than the shortest path already in the array, then update the value.
To start the second round of circulation, eliminate has found A path, namely 0, 2, to find A shortest path, find 3, the index of 5 vertices, namely A – F, set up corresponding location marker of the shortest path to true, update did not obtain the shortest path of the vertices of the shortest path, because the other has found the vertices of the shortest path has been found, You just update the shortest path from the newly found F reachable vertex path to A, and if the path through F is smaller than the shortest path that already exists in the array, then update the value.
Here F can reach G, f-g + a-f =12<99, so the shortest path to update A-g is 12, the second cycle ends, at this point the shortest path array is {0, 11, 7, 2, 99, 3, 12}, The flag bit array is {true, false, false, true, false, true, false}.
Started the third round of circulation, eliminate has found A path, namely 0, 2, 3, to find A shortest path, find seven, namely index for two vertices, namely A – C, set up corresponding location marker of the shortest path to true, the update did not obtain the shortest path of the vertices of the shortest path, because the other has found the vertices of the shortest path has been found, Here you just update the shortest path from the newly found C reachable vertex path to point A, and if the path through point C is smaller than the shortest path already in the array, then update the value.
Here C can reach B, c-b + a-c =11 =11, so the shortest path of A-B is not updated, the third round of the loop ends, at this point, the shortest path array is {0, 11, 7, 2, 99, 3, 12}, The flag bit array is {true, false, true, true, false, true, false}.
To start the fourth round of circulation, eliminate has found A path, namely 0, 2, 3, 7, to find A shortest path, here find 11, the index of 1 vertices, namely A – B, set up corresponding location marker of the shortest path to true, the update did not obtain the shortest path of the vertices of the shortest path, because the other has found the vertices of the shortest path has been found, Here you just update the shortest path from the newly found reachable vertex path to point A, and if the path through point B is smaller than the shortest path that already exists in the array, then update the value.
Here point B can reach E, b-e + a-b =18 < 99, so update the shortest path of A-e is 18, the fourth cycle ends, at this point the shortest path array is {0, 11, 7, 2, 18, 3, 12}, The flag bit array is {true, true, true, true, false, true, false}.
Start the fifth cycle, exclude the found path, namely 0, 2, 3, 7 and 11, find the shortest path of A, find 12, namely the vertex with index 6, namely a-g, set the shortest path flag of the corresponding position to true, update the shortest path of the vertex without the shortest path. Because the shortest paths to the other vertices already found are already found, we simply update the shortest path from the newly found G reachable vertex path to A. If the path through G is smaller than the shortest path that already exists in the array, we update the value.
Exclude the vertices found, where G point can reach E, g-E + a-g =18 =18, so the shortest path is not updated, the fifth cycle ends, at this point, the shortest path array is {0, 11, 7, 2, 18, 3, 12}, The flag bit array is {true, true, true, true, false, true, true}.
Start the sixth cycle, exclude the found paths, namely 0, 2, 3, 7, 11 and 12, find the shortest path of A, find 18, namely the vertex with index 4, namely a-e, set the shortest path flag of the corresponding position to true, update the shortest path of the vertex that has not obtained the shortest path. Because the shortest paths to the other vertices already found are already found, we simply update the shortest path from the newly found E reachable vertex path to A. If the path through E is smaller than the shortest path that already exists in the array, we update the value.
The found vertices are excluded, the shortest path is not updated, the fourth round of the loop ends, at this time the shortest path array is {0, 11, 7, 2, 18, 3, 12}, the flag bit array is {true, true, true, true, true}. At this point, the loop ends, Dijkstra algorithm ends, and the shortest path from vertex A to each vertex has been found, that is, the shortest path from A to {A,B,C,D,E,F,G} is {0, 11, 7, 2, 18, 3, 12}.
3. Floyd algorithm
3.1 the principle
Floyd algorithm, also known as interpolation method, is an algorithm that uses the idea of dynamic programming to find the shortest path between multiple source points in a given weighted graph. The result is the shortest distance between all nodes and the rest.
The general steps are as follows:
- Let the number of vertices in the graph be N. Firstly, we need to prepare a distance matrix S with length N. The element A [I][j]=sum in matrix S indicates that the shortest path from vertex I to vertex j is sum.
- Then the s-matrix is initialized. The value of vertex A [I][j] in the distance matrix S is the direct weight from vertex I to vertex J.
- Then to N S matrix cycle time update, updated, in the first k times if S matrix of a [I] [j] > [I] a [k] + [k] a [j], then update a [I] [j] = [I] a [k] + [k] a [j]. When the cycle is updated, the algorithm is complete and the shortest distance between all nodes and the rest nodes has been found.
Compared to Dijkstra’s algorithm, Floyd’s algorithm supports graphs with negative weighted edges, but cannot solve graphs with “negative weighted loops” (or “negative weighted loops”). In fact, if a graph has a “negative weighted loop” then the graph has no shortest path.
The time complexity of Floyd algorithm is also O(n^3^), and the space complexity is O(n^2^). The code is very simple, but the idea is very clever. All the possibilities are enumerated and compared one by one, and the minimum value is taken, so that the minimum value will be finally obtained.
3.2 Case Analysis
This case corresponds to the case in the implementation code below:
First, the distance matrix S is initialized as follows:
When k=0, the loop traverses the S-matrix to determine whether it is less than shortestPath[I][j], that is, all paths pass through point A. ShortestPath [I][0] + shortestPath[k][0]< shortestPath[I][j] ShortestPath [I][j]= shortestPath[I][0] + shortestPath[k][0]. The array after a large loop looks like this:
Then, after N major cycles, indicating that all vertices have been passed, the matrix is finally obtained as follows:
Realization of adjacency matrix weighted graph
The implementation here can construct a class to implement undirected weighted graphs based on adjacency matrix, and provide depth-first and breadth-first traversal methods, provide methods to obtain the number of edge sets, provide Prim and Kruskal methods to find the minimum spanning tree, and provide Dijkstra and Floyd methods to find the shortest path.
/** * undirected weighted graph adjacency matrix implementation * {@linkMatrixDijkstraAndFloyd(Object[], Edge[])} construct undirected weighted graph * {@linkMatrixDijkstraAndFloyd#DFS()} depth-first traversal of undirected weighted graphs * {@linkMatrixDijkstraAndFloyd#BFS()} breadth-first traversal of undirected weighted graphs * {@linkMatrixDijkstraAndFloyd#toString()} output undirected weighted graph * {@linkMatrixDijkstraAndFloyd#prim()} prim algorithm implements minimum spanning tree * {@linkMatrixDijkstraAndFloyd#kruskal()} kruskal algorithm to implement the minimum spanning tree * {@linkMatrixDijkstraAndFloyd#kruskalAndPrim()} MatrixDijkstraAndFloyd#kruskalAndPrim@linkMatrixDijkstraAndFloyd#getEdges()}@linkMatrixDijkstraAndFloyd#dijkstra(int)} ()} dijkstra obtains the shortest path from a specified vertex to all vertices * {@linkMatrixDijkstraAndFloyd#dijkstra(int, int)} dijkstra obtains the shortest path from the specified vertex to the specified vertex * {@linkMatrixDijkstraAndFloyd# Floyd ()} Floyd gets the shortest path from all vertices to all vertices * *@author lx
*/
public class MatrixDijkstraAndFloyd<E> {
/** * vertex array */
private Object[] vertexs;
/** * adjacency matrix */
private int[][] matrix;
/ * * * * /
private Edge<E>[] edges;
/** * Since it is a weighted graph, the upper limit of the weight value of an edge is set here. The maximum weight value of any edge cannot be greater than or equal to this value. In practical application, the value should be determined according to the actual situation */
private static final int NO_EDGE = 99;
/** * edge object that has weights and uses */ when building weighted undirected graphs
private static class Edge<E> {
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(a) {
return "Edge{" +
"from=" + from +
", to=" + to +
", weight=" + weight +
'} '; }}/** * create undirected weighted graph **@paramVertexs array of vertexs@paramEdges array of objects */
public MatrixDijkstraAndFloyd(Object[] vertexs, Edge<E>[] edges) {
// Initializes the edge array
this.edges = edges;
// Initialize the array of vertices and add vertices
this.vertexs = Arrays.copyOf(vertexs, vertexs.length);
// Initialize the edge matrix and prepopulate the edge information
this.matrix = new int[vertexs.length][vertexs.length];
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
if (i == j) {
this.matrix[i][j] = 0;
} else {
this.matrix[i][j] = NO_EDGE; }}}for (Edge<E> edge : edges) {
// Read the starting and ending vertex indexes of an edge
int p1 = getPosition(edge.from);
int p2 = getPosition(edge.to);
// Both symmetric points are set to edge.weight. Undirected graphs can be regarded as mutually reachable digraphs
this.matrix[p1][p2] = edge.weight;
this.matrix[p2][p1] = edge.weight; }}/** * Retrieves the index position of a vertex on an edge **@paramE, the value of the vertex *@returnThe index position of the array of vertices, or -1 - indicates that */ does not exist
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == e) {
returni; }}return -1;
}
/** * depth-first search traversal graph, similar to pre-order traversal of tree, */
public void DFS(a) {
// Create a new vertex access tag array, corresponding to each index corresponding to the same index of the vertex array vertices
boolean[] visited = new boolean[vertexs.length];
// Initialize that all vertices are not accessed
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++) {
if(! visited[i]) { DFS(i, visited); } } System.out.println(); }/** * The recursive implementation of depth-first search traversal graph is similar to the sequential traversal of a tree * so it mimics the sequential traversal of a tree and also borrows the stack structure, which uses the recursion of the method, implicitly borrows the stack **@paramI vertex index *@param*/
private void DFS(int i, boolean[] visited) {
visited[i] = true;
System.out.print(vertexs[i] + "");
// Traverses all the adjacent points of the vertex. If the adjacency is not visited, continue to recursively traverse the lead contact
for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
if(! visited[w]) { DFS(w, visited); }}}/** * breadth-first search graph, similar to tree sequence traversal * therefore mimics tree sequence traversal, also borrowing queue structure */
public void BFS(a) {
// Secondary queue
Queue<Integer> indexLinkedList = new LinkedList<>();
// Create a new vertex access tag array, corresponding to each index corresponding to the same index of the vertex array vertices
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++) {
if(! visited[i]) { visited[i] =true;
System.out.print(vertexs[i] + "");
indexLinkedList.add(i);
}
if(! indexLinkedList.isEmpty()) {//j index out of the queue
Integer j = indexLinkedList.poll();
// continue to access j's adjacency
for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) {
if(! visited[k]) { visited[k] =true;
System.out.print(vertexs[k] + "");
// Continue to queue
indexLinkedList.add(k);
}
}
}
}
System.out.println();
}
/** * returns the index of the first adjacent vertex to vertex v, or -1 ** on failure@paramV The index of vertex v in the array *@returnReturns the index of the first adjacent vertex of vertex v, or -1 */ on failure
private int firstVertex(int v) {
// If the index is out of range, -1 is returned
if (v < 0 || v > (vertexs.length - 1)) {
return -1;
}
/* According to the rule of adjacency matrix: the vertex index v corresponds to the matrix[v][I] line of the edge matrix * starting from I =0 */
for (int i = 0; i < vertexs.length; i++) {
if(matrix[v][i] ! =0&& matrix[v][i] ! = NO_EDGE) {returni; }}return -1;
}
/** * returns the index of the next adjacent vertex of vertex v relative to w, or -1 ** on failure@paramV Vertex index *@paramW The first adjacency index *@returnReturns the index of the next adjacent vertex of vertex v relative to w, or -1 */ on failure
private int nextVertex(int v, int w) {
// If the index is out of range, -1 is returned
if (v < 0 || v > (vertexs.length - 1) || w < 0 || w > (vertexs.length - 1)) {
return -1;
}
/* According to the rule of adjacency matrix: the vertex index v corresponds to the matrix[v][I] of the two-dimensional edge matrix * * Because the index of the adjacency point w has been obtained, so I =w+1 to find */
for (int i = w + 1; i < vertexs.length; i++) {
if(matrix[v][i] ! =0&& matrix[v][i] ! = NO_EDGE) {returni; }}return -1;
}
/** * output graph **@returnOutput the graph string */
@Override
public String toString(a) {
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 algorithm for minimum spanning tree */
public void prim(a) {
System.out.println("prim: ");
// The corresponding node should be connected to the precursor node, used for output
// The default is 0, that is, the first node
int[] mid = new int[matrix.length];
// If a vertex is connected as a terminal vertex, the position should be true
// The first vertex is joined by default
boolean[] connected = new boolean[matrix.length];
connected[0] = true;
// Store the shortest distance between unconnected vertices and connected vertices (minimum weight)
int[] dis = new int[matrix.length];
// Copy the weights of the first row of the matrix from other vertices to 0
System.arraycopy(matrix[0].0, dis, 0, matrix.length);
// Storage path length
int sum = 0;
// Minimum weight
int min;
/* By default, the first vertex is already found, so at most n-1 large loop */
for (int k = 1; k < matrix.length; k++) {
min = NO_EDGE;
// Index of vertices with minimum weights
int minIndex = 0;
/* Find the least weighted unjoined vertex index */
for (int i = 1; i < matrix.length; i++) {
// Exclude connected vertices with weights equal to 0, where weights equal to 0 mean that all vertices in the generated minimum spanning tree failed to connect to the vertex
if(! connected[i] && dis[i] ! =0&& dis[i] < min) { min = dis[i]; minIndex = i; }}// If the graph is not found, the graph may not be connected, and the minimum spanning tree is meaningless
if (minIndex == 0) {
return;
}
// Weights and increments
sum += min;
// The index value of the newly connected vertex becomes true, indicating that the vertex has been connected, and the vertex will be skipped in the subsequent judgment
connected[minIndex] = true;
// Outputs the weight of the corresponding precursor vertex to the minimum vertex
System.out.println("\t" + vertexs[mid[minIndex]] + "- >" + vertexs[minIndex] + "Weight." + min);
/* The minimum weights from all other vertices to the connected vertex have been calculated before the new vertex minIndex is added, so just update the minIndex of other unconnected vertices to see if there are any shorter weights. If so, update the minIndex to find the vertex with the least weight from the connected vertex */
for (int i = 1; i < matrix.length; i++) {
// If the vertex is not connected
if(! connected[i]) {/* If the weight of the new vertex to unconnected vertex I is not zero and is less than the weight of the original vertex to unconnected vertex I, then update the minimum weight of the corresponding position */
if(matrix[minIndex][i] ! =0 && dis[i] > matrix[minIndex][i]) {
// Update the minimum weight
dis[i] = matrix[minIndex][i];
// Update the precursor node index to the newly added node index
mid[i] = minIndex;
}
}
}
}
System.out.println("\t" + "sum: " + sum);
}
/** * Kruskal algorithm to find the minimum spanning tree traditional implementation, requires to know the number of edge sets, and the vertex array */
public void kruskal(a) {
System.out.println("Kruskal: ");
// Since we saved the number of edge sets when creating the graph, we can use it directly
//Edge[] edges = getEdges();
//this.edges=edges;
// Sort the number of edge sets
Arrays.sort(this.edges, Comparator.comparingInt(o -> o.weight));
// Used to hold the index of the end point of each vertex in the existing minimum spanning tree
int[] vends = new int[this.edges.length];
// The index range of edges is [0,this.edges. Length-1], so padding edges. Length means no edges
Arrays.fill(vends, this.edges.length);
int sum = 0;
for (Edge<E> edge : this.edges) {
// Get the starting index of edge I from
int from = getPosition(edge.from);
// get the index to the end of the I edge
int to = getPosition(edge.to);
// Get the vertex from the endpoint in the existing minimum spanning tree
int m = getEndIndex(vends, from);
// Get the endpoint of vertex to in existing minimum spanning tree
int n = getEndIndex(vends, to);
/ / if m! =n, which means that no loop is formed, so it can be added. Otherwise, it can be directly skipped to determine the next edge
if(m ! = n) {// Add set the original endpoint index m to n in the existing minimum spanning tree
vends[m] = n;
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));
}
/** * returns the vertex index itself ** if there is no endpoint@paramEnd point of vends vertex in minimum spanning tree *@paramI vertex index *@returnThe endpoint of the vertex index I returns the vertex index itself */ if there is no endpoint
private int getEndIndex(int[] vends, int i) {
// We use the logic of loop search to find the final destination
while(vends[i] ! =this.edges.length) {
i = vends[i];
}
return i;
}
/** * If there is no existing edge set, then obtain the edge set in the graph according to the adjacency matrix structure **@returnThe number of edge sets of the graph */
private Edge[] getEdges() {
List<Edge> edges = new ArrayList<>();
/* Only half of the array is traversed */
for (int i = 0; i < vertexs.length; i++) {
for (int j = i + 1; j < vertexs.length; j++) {
// If there are edges
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 combines Prim algorithm. You don't need to know the edge set, just that the matrix array, like the vertex array *, is the least weighted edge, but has a default starting vertex, which can be any value between [0, number of vertices -1], and find the least weighted edge. * There may be bugs, not found so far */
public void kruskalAndPrim(a) {
System.out.println("kruskalAndPrim: ");
// The index of vertices carried by found edges will be true, and the index of vertices carried by other unfound edges will be false
boolean[] connected = new boolean[matrix.length];
// Select the first vertex as the starting point to find the smallest edge containing the vertex
connected[0] = true;
int sum = 0, n1 = 0, n2 = 0;
// Minimum weight
int min;
while (true) {
min = NO_EDGE;
/* To find the edge with the lowest weight of all edges with found vertices, find only half of the symmetric matrix */
/ / the first dimension
for (int i = 0; i < matrix.length; i++) {
/ / the second dimension
for (int j = i + 1; j < matrix.length; j++) {
If both vertices of a certain edge are found, then if the edge is counted, it will definitely form a ring
// Find the lowest weight edge left
if(matrix[i][j] ! =0&& connected[i] ! = connected[j] && matrix[i][j] < min) { min = matrix[i][j]; n1 = i; n2 = j; }}}// If the minimum weight is not found, the graph may not be connected, or the search has been completed, directly return
if (min == NO_EDGE) {
System.out.println("\t" + "sum:" + sum);
return;
}
// Set both vertices corresponding to found edges to true
connected[n1] = true;
connected[n2] = true;
// Outputs the edges and minimum weights found
System.out.println("\t" + vertexs[n1] + "- >" + vertexs[n2] + "Weight."+ min); sum += min; }}/** * Dijkstra algorithm for shortest path. * *@paramStart Indicates the start vertex index. The shortest path from vertex vs vertex to other vertices. * /
public void dijkstra(int start) {
checkIndex(start);
int[] shortestPathance = getShortestDistance(start, vertexs.length);
// Prints the result of Dijkstra's shortest path
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 for the shortest path **@paramStart Start point *@paramEnd =vertexs.length; end=vertexs.length@returnThe shortest weight from the starting vertex to any other point or specified point */
private int[] getShortestDistance(int start, int end) {
/*1, this array stores the starting vertex to other points weight */
int[] shortestPathance = new int[vertexs.length];
// Initialize the data
// First set the shortest path from start to vertex I as the weight from start to vertex I.
System.arraycopy(matrix[start], 0, shortestPathance, 0, matrix.length);
/*2. A value of true indicates that the shortest path from the corresponding vertex to the starting vertex has been successfully obtained. * /
boolean[] shortest = new boolean[vertexs.length];
// The path from the start point to its own is already found, 0
shortest[start] = true;
Vertexs. length-1; Find the shortest path from the starting point to one vertex at a time. * /
int k;
int min;
for (int i = 1; i < vertexs.length; i++) {
k = 0;
// Find the current minimum path;
min = NO_EDGE;
for (int j = 0; j < vertexs.length; j++) {
// Find the vertex (k) closest to start after excluding the shortest paths already found.
if (!shortest[j] && shortestPathance[j] < min) {
min = shortestPathance[j];
k = j;
}
}
The shortest path from the start point to the new vertex k has been found
shortest[k] = true;
if(end ! = vertexs.length && k == end) {break;
}
// Update the shortest paths of vertices that do not have the shortest paths, because the shortest paths of other vertices that have been found are already found. This refers to the need to update the paths of newly found reachable vertices.
for (int j = 0; j < vertexs.length; j++) {
int tmp = matrix[k][j];
// Exclude found shortest paths, exclude unconnected paths, and exclude paths equal to 0 (after connecting itself)
If the new shortest path is shorter than the previous one, update the shortest path.
if(! shortest[j] && tmp ! = NO_EDGE && tmp ! =0&& ((tmp = min + tmp) < shortestPathance[j])) { shortestPathance[j] = tmp; }}}return shortestPathance;
}
/** * index check **@paramIndex Multiple indexes */
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 for shortest path. * *@paramStart Indicates the start vertex index. *@paramEnd Indicates the end point index */
public void dijkstra(int start, int end) {
checkIndex(start, end);
int[] shortestPathance = getShortestDistance(start, end);
// Prints the result of Dijkstra's shortest path
System.out.println("Dijkstra(" + vertexs[start] + "- >" + vertexs[end] + ") shortest path :" + shortestPathance[end]);
}
/** ** Floyd algorithm to get all vertices to all the shortest path, the code is very simple, the idea is very clever */
public void floyd(a) {
// Path matrix (two-vertex shortest path, i.e., minimum weight)
int[][] shortestPath = new int[matrix.length][matrix.length];
/* Initializes data */
for (int i = 0; i < matrix.length; i++) {
System.arraycopy(matrix[i], 0, shortestPath[i], 0, vertexs.length);
}
// Calculate the shortest path
for (int k = 0; k < matrix.length; k++) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
NO_EDGE = NO_EDGE = NO_EDGE = NO_EDGE = NO_EDGE
int tmp = (shortestPath[i][k] == NO_EDGE || shortestPath[k][j] == NO_EDGE) ? NO_EDGE : (shortestPath[i][k] + shortestPath[k][j]);
ShortestPath [I][j] shortestPath[I][j]
if (shortestPath[i][j] > tmp) {
// The shortest path from I to j is set to the smaller path through kshortestPath[i][j] = tmp; }}}}/* Output path matrix */
System.out.println("Floyd: ");
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) {
// Vertex array
Character[] vexs = {'A'.'B'.'C'.'D'.'E'.'F'.'G'};
// Edge array, weighted values
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)};
/ / build
MatrixDijkstraAndFloyd<Character> matrixDijkstraAndFloyd = new MatrixDijkstraAndFloyd<Character>(vexs, edges);
/ / output figure
System.out.println(matrixDijkstraAndFloyd);
Depth-first traversal
matrixDijkstraAndFloyd.DFS();
// width first traversal
matrixDijkstraAndFloyd.BFS();
//Prim outputs the minimum spanning tree
matrixDijkstraAndFloyd.prim();
// The Kruskal algorithm outputs the minimum spanning tree
matrixDijkstraAndFloyd.kruskal();
//Kruskal algorithm combined with Prim algorithm output minimum spanning tree, there may be a Bug, so far not found
matrixDijkstraAndFloyd.kruskalAndPrim();
// Dijkstra obtains the shortest distance between one index vertex and other vertices
// This parameter is an index, which can also be a vertex. You need to modify the code slightly to obtain the index of the vertex
matrixDijkstraAndFloyd.dijkstra(0);
// Dijkstra gets the shortest distance from one vertex to another
matrixDijkstraAndFloyd.dijkstra(2.0);
// The Floyd algorithm gets the shortest path from all vertices to all verticesmatrixDijkstraAndFloyd.floyd(); }}Copy the code5 adjacency list weighted graph implementation
The implementation here can construct a class that implements undirected weighted graphs based on adjacency lists; In addition, it provides depth-first traversal and breadth-first traversal methods, provides the method to obtain the number of edge sets, provides Prim and Kruskal methods to find the minimum spanning tree, and provides Dijkstra and Floyd methods to find the shortest path.
/** * undirected weighted graph adjacency list implementation * {@linkListDijkstraAndFloyd(Object[], Edge[])} construct undirected weighted graph * {@linkListDijkstraAndFloyd#DFS()} depth-first traversal of undirected weighted graph * {@linkListDijkstraAndFloyd#BFS()} breadth first traversal undirected weighted graph * {@linkListDijkstraAndFloyd#toString()} output undirected weighted graph * {@linkListDijkstraAndFloyd#prim()} ListDijkstraAndFloyd#prim@linkListDijkstraAndFloyd#kruskal()} kruskal algorithm to implement the minimum spanning tree * {@linkListDijkstraAndFloyd#getEdges()}@linkListDijkstraAndFloyd#dijkstra(int)} ()} get the shortest path to all vertices * {ListDijkstraAndFloyd#dijkstra(int)} ()}@linkListDijkstraAndFloyd#dijkstra(int, int)} get the shortest path to the specified vertex * {ListDijkstraAndFloyd#dijkstra(int, int)}@linkListDijkstraAndFloyd# Floyd ()} Floyd gets the shortest path from all vertices to all vertices * *@author lx
*/
public class ListDijkstraAndFloyd<E> {
/** * vertex class **@param <E>
*/
private class Node<E> {
/** * vertex information */
E data;
/** * points to the first edge attached to the vertex */
LNode firstLNode;
public Node(E data, LNode firstLNode) {
this.data = data;
this.firstLNode = firstLNode; }}/** * edge table node class */
private class LNode {
/** * The index position of the vertex to which the edge points */
int vertex;
/** * The weight of the edge */
int weight;
/**
* 指向下一条边的指针
*/
LNode nextLNode;
}
/** * edge object that has weights and uses */ when building weighted undirected graphs
private static class Edge<E> {
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(a) {
return "Edge{" +
"from=" + from +
", to=" + to +
", weight=" + weight +
'} '; }}/** * vertex array */
private Node<E>[] vertexs;
/** * edge array */
private Edge<E>[] edges;
/** * Since it is a weighted graph, the upper limit of the weight value of an edge is set here. The maximum weight value of any edge cannot be greater than or equal to this value. In practical application, the value should be determined according to the actual situation */
private static final int NO_EDGE = 99;
/** * create undirected weighted graph **@paramVexs Array of vertices *@paramEdges the two-dimensional array */
public ListDijkstraAndFloyd(E[] vexs, Edge<E>[] edges) {
this.edges = edges;
/* Initializes the vertices array and adds vertices */
vertexs = new Node[vexs.length];
for (int i = 0; i < vertexs.length; i++) {
vertexs[i] = new Node<>(vexs[i], null);
}
/* Initializes the edge list and adds edge nodes to the end of the edge list using the tail interpolation method */
for (Edge<E> edge : edges) {
// Read the starting and ending vertex indexes of an edge
int p1 = getPosition(edge.from);
int p2 = getPosition(edge.to);
int weight = edge.weight;
/* Where edge nodes need to be added to each other, undirected graphs can be regarded as mutually reachable directed graphs */
// Initialize lnode1
LNode lnode1 = new LNode();
lnode1.vertex = p2;
lnode1.weight = weight;
// link LNode to "end of list where p1 is"
if (vertexs[p1].firstLNode == null) {
vertexs[p1].firstLNode = lnode1;
} else {
linkLast(vertexs[p1].firstLNode, lnode1);
}
// Initialize the lnode2 side node
LNode lnode2 = new LNode();
lnode2.vertex = p1;
lnode2.weight = weight;
// link lnode2 to "end of list where p2 is"
if (vertexs[p2].firstLNode == null) {
vertexs[p2].firstLNode = lnode2;
} else{ linkLast(vertexs[p2].firstLNode, lnode2); }}}/** * Retrieves the index position of a vertex on an edge **@paramE, the value of the vertex *@returnThe index position of the array of vertices, or -1 - indicates that */ does not exist
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i].data == e) {
returni; }}return -1;
}
/** * link the lnode node to the end of the edge list, using the tail method **@paramFirst side table header *@paramNode Node to be added */
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(a) {
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 depth-first search traversal graph is similar to the sequential traversal of a tree * so it mimics the sequential traversal of a tree and also borrows the stack structure, which uses the recursion of the method, implicitly borrows the stack **@paramI vertex index *@param*/
private void DFS(int i, boolean[] visited) {
// index The index is marked true to indicate that it has been accessed
visited[i] = true;
System.out.print(vertexs[i].data + "");
// Get the edge header of this vertex
LNode node = vertexs[i].firstLNode;
// Loop over the adjacent points of the vertex, recursively searching in the same way
while(node ! =null) {
if (!visited[node.vertex]) {
DFS(node.vertex, visited);
}
node = node.nextLNode;
}
}
/** * depth-first search traversal graph, similar to pre-order traversal of tree, */
public void DFS(a) {
// Create a new vertex access tag array, corresponding to each index corresponding to the same index of the vertex array vertices
boolean[] visited = new boolean[vertexs.length];
// Initialize that all vertices are not accessed
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("DFS: ");
System.out.print("\t");
/* Loop search */
for (int i = 0; i < vertexs.length; i++) {
// If the vertex of the corresponding index is marked false, the vertex is searched
if (!visited[i]) {
DFS(i, visited);
}
}
/* If the vertex access tag array is set to true, the search is complete
System.out.println();
}
/** * breadth-first search graph, similar to tree sequence traversal * therefore mimics tree sequence traversal, also borrowing queue structure */
public void BFS(a) {
// Secondary queue
Queue<Integer> indexLinkedList = new LinkedList<>();
// Create a new vertex access tag array, corresponding to each index corresponding to the same index of the vertex array vertices
boolean[] visited = new boolean[vertexs.length];
// Initialize that all vertices are not accessed
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++) {
// If the accessor is false, set it to true to indicate access, and then access begins
if(! visited[i]) { visited[i] =true;
System.out.print(vertexs[i].data + "");
indexLinkedList.add(i);
}
// Check whether the queue has a value
if(! indexLinkedList.isEmpty()) {/ / out of the queue
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 + "");
// Continue to queue
indexLinkedList.add(k);
}
node = node.nextLNode;
}
}
}
System.out.println();
}
/** * Prim algorithm for minimum spanning tree */
public void prim(a) {
System.out.println("prim: ");
// The corresponding node should be connected to the precursor node, used for output
// The default is 0, that is, the first node
int[] mid = new int[vertexs.length];
int start = 0;
int min, tmp, sum = 0;
int num = vertexs.length;
// The weights of edges between vertices
// Store the shortest distance between unconnected vertices and connected vertices (minimum weight)
int[] dis = new int[num];
// Initialize "vertex weights array",
// Initialize the weight of each vertex to the weight from "start vertex" to "this vertex".
// First store the weights of other vertices to 0 indexed vertices
for (int i = 0; i < num; i++) {
dis[i] = getWeight(start, i);
}
// If a vertex is connected as a terminal vertex, the position should be true
// The first vertex is joined by default
boolean[] connected = new boolean[vertexs.length];
connected[0] = true;
/* By default, the first vertex is already found, so at most n-1 large loop */
for (int k = 1; k < num; k++) {
min = NO_EDGE;
// Index of vertices with minimum weights
int minIndex = 0;
// Find the vertex with the lowest weight among the unadded vertices in the minimum spanning tree.
for (int i = 1; i < vertexs.length; i++) {
// Exclude connected vertices with weights equal to 0, because the default vertex points to itself with weights equal to 0
if(! connected[i] && dis[i] ! =0&& dis[i] < min) { min = dis[i]; minIndex = i; }}// If the graph is not found, the graph may not be connected, and the minimum spanning tree is meaningless
if (minIndex == 0) {
return;
}
// Weights and increments
sum += min;
// The index value of the newly connected vertex becomes true, indicating that the vertex has been connected, and the vertex will be skipped in the subsequent judgment
connected[minIndex] = true;
// Outputs the weight of the corresponding precursor vertex to the minimum vertex
System.out.println("\t" + vertexs[mid[minIndex]].data + "- >" + vertexs[minIndex].data + "Weight." + min);
/* The minimum weights from all other vertices to the connected vertex have already been calculated before minIndex is added to the new vertex, so just update the minIndex to see if there are any shorter weights from other vertices to the newly connected vertex. If so, update the minIndex to find the vertex with the least weight from the connected vertex
for (int i = 1; i < num; i++) {
// If the vertex is not connected
if(! connected[i]) {// Get the weight from minindex vertex to unconnected vertex I
tmp = getWeight(minIndex, i);
/* If the weight of the new vertex to unconnected vertex I is not zero and is less than the weight of the original vertex to unconnected vertex I, then update the minimum weight of the corresponding position */
if(tmp ! =0 && dis[i] > tmp) {
dis[i] = tmp;
// Update the precursor node index to the newly added node index
mid[i] = minIndex;
}
}
}
}
System.out.println("\t" + "sum: " + sum);
}
/** * try to get the weight of the edge from start to end@paramStart *@paramEnd edge end *@returnReturn weight; Returns 0 if the start and end are the same; If there is no edge between the beginning and end of an edge, NO_EDGE */ is returned
private int getWeight(int start, int end) {
// If start=end, 0 is returned
if (start == end) {
return 0;
}
// Gets the first value of the edge list for this vertex
LNode node = vertexs[start].firstLNode;
// loop through the edge table to see if it can find the corresponding index =end, 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 implementation of adjacency matrix and adjacency list is exactly the same */
public void kruskal(a) {
System.out.println("Kruskal: ");
// Since we saved the number of edge sets when creating the graph, we can use it directly
//Edge[] edges = getEdges();
//this.edges=edges;
// Sort the number of edge sets
Arrays.sort(this.edges, Comparator.comparingInt(o -> o.weight));
// Used to hold the index of the end point of each vertex in the existing minimum spanning tree
int[] vends = new int[this.edges.length];
// The index range of edges is [0,this.edges. Length-1], so padding edges. Length means no edges
Arrays.fill(vends, this.edges.length);
int sum = 0;
for (Edge<E> edge : this.edges) {
// Get the starting index of edge I from
int from = getPosition(edge.from);
// get the index to the end of the I edge
int to = getPosition(edge.to);
// Get the vertex from the endpoint in the existing minimum spanning tree
int m = getEndIndex(vends, from);
// Get the endpoint of vertex to in existing minimum spanning tree
int n = getEndIndex(vends, to);
/ / if m! =n, which means that no loop is formed, so it can be added. Otherwise, it can be directly skipped to determine the next edge
if(m ! = n) {// Add set the original endpoint index m to n in the existing minimum spanning tree
vends[m] = n;
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));
}
/** * returns the vertex index itself ** if there is no endpoint@paramEnd point of vends vertex in minimum spanning tree *@paramI vertex index *@returnThe endpoint of the vertex index I returns the vertex index itself */ if there is no endpoint
private int getEndIndex(int[] vends, int i) {
// We use the logic of loop search to find the final destination
while(vends[i] ! =this.edges.length) {
i = vends[i];
}
return i;
}
/** * If there is no existing edge set, then get the edge set in the graph according to the adjacency list structure **@returnThe number of edge sets of the graph */
private Edge[] getEdges() {
List<Edge> edges = new ArrayList<>();
// Iterate over the vertices array
for (int i = 0; i < vertexs.length; i++) {
LNode node = vertexs[i].firstLNode;
while(node ! =null) {
// Add the edge where the starting index is smaller than the end index
if (node.vertex > i) {
edges.add(newEdge<>(vertexs[i].data, vertexs[node.vertex].data, node.weight)); } node = node.nextLNode; }}return edges.toArray(new Edge[0]);
}
/** * Dijkstra algorithm for shortest path. * *@paramStart Indicates the start vertex index. The shortest path from vertex vs vertex to other vertices. * /
public void dijkstra(int start) {
checkIndex(start);
int[] distance = getShortestDistance(start, vertexs.length);
// Prints the result of dijkstra's shortest path
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 for shortest path. * *@paramStart Indicates the start vertex index. *@paramEnd Indicates the end point index */
public void dijkstra(int start, int end) {
checkIndex(start, end);
int[] shortestPathance = getShortestDistance(start, end);
// Prints the result of dijkstra's shortest path
System.out.println("Dijkstra(" + vertexs[start].data + "- >" + vertexs[end].data + ") shortest path :" + shortestPathance[end]);
}
/** * Dijkstra algorithm for the shortest path **@paramStart Start point *@paramEnd =vertexs.length; end=vertexs.length@returnThe shortest weight from the starting vertex to any other point or specified point */
private int[] getShortestDistance(int start, int end) {
/*1, this array stores the starting vertex to other points weight */
int[] distance = new int[vertexs.length];
// Initialize the data
for (int i = 0; i < vertexs.length; i++) {
// First set the shortest path from start to vertex I as the weight from start to vertex I.
distance[i] = getWeight(start, i);
}
/*2. A position where true indicates that the shortest path from the vertex to the starting vertex has been successfully obtained. * /
boolean[] shortest = new boolean[vertexs.length];
// The path from the start point to its own is already found, 0
shortest[start] = true;
Vertexs. length-1; Find the shortest path from the starting point to one vertex at a time. * /
int k;
int min;
for (int i = 1; i < vertexs.length; i++) {
k = 0;
// Find the current minimum path;
min = NO_EDGE;
for (int j = 0; j < vertexs.length; j++) {
// Find the vertex (k) closest to start after excluding the shortest paths already found.
if (!shortest[j] && distance[j] < min) {
min = distance[j];
k = j;
}
}
The shortest path from the start point to the new vertex k has been found
shortest[k] = true;
if(end ! = vertexs.length && k == end) {break;
}
// Update the shortest paths of vertices that do not have the shortest paths, because the shortest paths of other vertices that have been found are already found. This refers to the need to update the paths of newly found reachable vertices.
for (int j = 0; j < vertexs.length; j++) {
int tmp = getWeight(k, j);
// Exclude found shortest paths, exclude unconnected paths, and exclude paths equal to 0 (after connecting itself)
If the new shortest path is shorter than the previous one, update the shortest path.
if(! shortest[j] && tmp ! = NO_EDGE && tmp ! =0&& ((tmp = min + tmp) < distance[j])) { distance[j] = tmp; }}}return distance;
}
/** * index check **@paramIndex Multiple indexes */
private void checkIndex(int. index) {
for (int i : index) {
if (i < 0 || i >= vertexs.length) {
throw new ArrayIndexOutOfBoundsException("Index out of bounds :"+ i); }}}/** * The Floyd algorithm obtains the shortest path from all vertices to all vertices, which is basically the same as the implementation of adjacency matrix */
public void floyd(a) {
// Path matrix (two-vertex shortest path, i.e., minimum weight)
int[][] shortestPath = new int[vertexs.length][vertexs.length];
/* Initializes data */
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
// Get the direct weights of two points
// If you call this method frequently, you can create a weight matrix of the object to hold the weights. This is not done for simplicityshortestPath[i][j] = getWeight(i, j); }}// Calculate the shortest path
for (int k = 0; k < vertexs.length; k++) {
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
NO_EDGE = NO_EDGE = NO_EDGE = NO_EDGE = NO_EDGE
int tmp = (shortestPath[i][k] == NO_EDGE || shortestPath[k][j] == NO_EDGE) ? NO_EDGE : (shortestPath[i][k] + shortestPath[k][j]);
ShortestPath [I][j] shortestPath[I][j]
if (shortestPath[i][j] > tmp) {
// The shortest path from I to j is set to the smaller path through kshortestPath[i][j] = tmp; }}}}/* Output path matrix */
System.out.println("Floyd: ");
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
System.out.print("\t"+ shortestPath[i][j]); } System.out.println(); }}public static void main(String[] args) {
// Vertex array
Character[] vexs = {'A'.'B'.'C'.'D'.'E'.'F'.'G'};
// Edge array, weighted values
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)};
/ / build
ListDijkstraAndFloyd<Character> listDijkstraAndFloyd = new ListDijkstraAndFloyd<Character>(vexs, edges);
/ / output figure
System.out.println(listDijkstraAndFloyd);
Depth-first traversal
//DFS:
//A C B E G F D
listDijkstraAndFloyd.DFS();
// width first traversal
//BFS:
//A C D F B G E
listDijkstraAndFloyd.BFS();
//Prim algorithm for minimum spanning tree
listDijkstraAndFloyd.prim();
//Kruskal algorithm for minimum spanning tree
listDijkstraAndFloyd.kruskal();
// Dijkstra obtains the shortest distance between one index vertex and other vertices
// This parameter is an index, which can also be a vertex. You need to modify the code slightly to obtain the index of the vertex
listDijkstraAndFloyd.dijkstra(0);
// Dijkstra gets the shortest distance from one vertex to another
listDijkstraAndFloyd.dijkstra(2.0);
// The Floyd algorithm gets the shortest path from all vertices to all verticeslistDijkstraAndFloyd.floyd(); }}Copy the codeRelated references:
- “The algorithm”
- Data Structures and Algorithms
- Big Talk Data Structure
- Diagram of algorithms
If you don’t understand or need to communicate, you can leave a message. In addition, I hope to like, collect, pay attention to, I will continue to update a variety of Java learning blog!