©2020-2024 ioDraw All rights reserved
<> introduce
and Dijkstra Same algorithm , Freud (Floyd) The algorithm is also an algorithm for finding the shortest path of vertices in a given weighted graph , That is, calculate the shortest path between each vertex , Dijestra algorithm is used to calculate the shortest path from a vertex to other vertices . Every vertex of Freudian algorithm is the starting point , Therefore, we need to treat each vertex as an accessed vertex , Find the shortest path from each vertex to other vertices .
<> algorithm analysis
1, Set vertex vi reach vk The shortest path is known to be Lik, vertex vk reach vj The shortest path is Lkj, vertex vi reach vj The path to is Lij, be vi reach vj The shortest path is ：min(Lik+Lkj),vk The value of is all vertices , Can be obtained vi reach vj Shortest path .
2, as for vi reach vk Shortest path Lik perhaps vk reach vj Shortest path Lkj, Is obtained in the same way .
<> Algorithm application
There are seven villages （A,B,C,D,E,F,G）, The distance between villages is indicated by a sideline （ power ）, How to calculate the shortest path from each village to other villages .
package algorithm; import java.util.Arrays; /** * @author taoke * @desc Freudian algorithm
* @email 1504806660@qq.com * @date 2022/1/27 */ public class Floyd { private
static final int N = 65535; public static void main(String[] args) { char[]
vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; int[][] matrix = { {N, 5, 7, N,
N, N, 2}, {5, N, N, 9, N, N, 3}, {7, N, N, N, 8, N, N}, {N, 9, N, N, N, 4, N},
{N, N, 8, N, N, 5, 4}, {N, N, N, 4, 5, N, 6}, {2, 3, N, N, 4, 6, N} }; Graph
graph = new Graph(vertex, matrix, vertex.length); graph.floyd(); graph.show();
} public static class Graph { /** * vertex */ private final char[] vertex; /** *
Distance from each vertex to other vertices , It is also the final result */ private final int[][] matrix; /** * The precursor node saved to the target vertex */
private final int[][] pre; /** * initialization * * @param length Vertex length size * @param matrix
adjacency matrix * @param vertex vertex array */ public Graph(char[] vertex, int[][] matrix, int
length) { this.vertex = vertex; this.matrix = matrix; this.pre = new
int[length][length]; // yes pre Array initialization , Stored is the subscript of the precursor vertex for (int i = 0; i < length; i++) {
Arrays.fill(pre[i], i); } } public void show() { for (int i = 0; i <
matrix.length; i++) { System.out.println(); for (int j = 0; j < matrix.length;
j++) { System.out.print(vertex[i] + "->" + vertex[j] + "=" + matrix[i][j] +
"\t"); } System.out.println(); } } /** * Freudian algorithm */ public void floyd() { int
len;// Variable save distance for (int i = 0; i < matrix.length; i++) { for (int j = 0; j <
matrix.length; j++) { for (int k = 0; k < matrix.length; k++) { len =
matrix[i][j] + matrix[i][k]; if (len < matrix[j][k]) { matrix[j][k] =
len;// Update distance pre[j][k] = pre[i][k];// Update precursor node } } } } } } }
<> result
Technology