<>14.9 Freudian algorithm （Floyd）

Floyd Algorithm Introduction ：
1, and Dijkstra Same algorithm , Freud (Floyd) The algorithm is also used to find the shortest path between vertices in a given weighted graph
2, Freudian algorithm (Floyd) Calculate the shortest path between vertices in the graph , Dijestra algorithm is used to calculate the shortest path from a vertex to other vertices in the graph
3, Freudian algorithm VS Dijkstra's algorithm ： Dijestra algorithm through the selected visited vertices , Find the starting access vertex to other vertices
Shortest path ; Every vertex in Freud's algorithm is the starting point , Therefore, each vertex needs to be regarded as the visited vertex , Find from each The shortest path from one vertex to another

Floyd algorithm analysis ：
1, Set vertex vi To vertex vk The shortest path is known to be Lik, vertex vk reach vj The shortest path is known to be Lkj, vertex vi reach vj The path to is Lij, be
vi reach vj The shortest path is ：min((Lik+Lkj),Lij),vk The value of is all vertices in the graph , 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

Floyd Algorithm practice ： Find the shortest path from each village to other villages

package com.atguigu22.floyd; import java.lang.reflect.Array; import java.util.
Arrays; /** * @author peng * @date 2021/12/7 - 16:32 * <p> *
Use Freud algorithm to find the shortest path from each village to other villages */ public class FloydAlgorithm { public static void
main(String[] args) { char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; int[]
[] matrix = new int[vertex.length][vertex.length]; final int N = 65535; matrix[0
] = new int[]{0, 5, 7, N, N, N, 2}; matrix = new int[]{5, 0, N, 9, N, N, 3};
matrix = new int[]{7, N, 0, N, 8, N, N}; matrix = new int[]{N, 9, N, 0, N,
4, N}; matrix = new int[]{N, N, 8, N, 0, 5, 4}; matrix = new int[]{N, N, N
, 4, 5, 0, 6}; matrix = new int[]{2, 3, N, N, 4, 6, 0}; Graph graph = new
Graph(vertex.length, matrix, vertex); graph.floyd(); graph.show(); } } /** *
Create diagram */ class Graph { private char[] vertex;// The storage node is an array private int[][] dis;
// Saves the distance from the starting vertex to each vertex private int[][] pre;// Saves the leading vertex that reaches the target vertex /** * @param length: Number of villages
* @param matrix： Two dimensional array information between villages * @param vertex： The name of the village */ public Graph(int length,
int[][] matrix, char[] vertex) { this.vertex = vertex; this.dis = matrix; this.
pre= new int[length][length]; // yes pre Initialize array for (int i = 0; i < length; i++) {
// At the beginning , The precursor node of each village is itself Arrays.fill(pre[i], i); } } /** * display dis Array and pre array */
public void show() { char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; for (
int i = 0; i < vertex.length; i++) { for (int j = 0; j < pre.length; j++) {
System.out.print(vertex[pre[i][j]] + "\t"); } System.out.println(); for (int k =
0; k < dis.length; k++) { System.out.print(vertex[i] + " reach " + vertex[k] +
" The shortest path is ：" + dis[i][k] + "\t"); } System.out.println(); } } /** * The main idea of realizing Freudian algorithm ：
* Suppose there is i,k, j Three villages , Possible routes are ：i--->, Or i--->k--->j *
In other words, there are two routes , One is direct i Village direction j village , Another is i Village first k village , Again j village , That is to say k Villages as intermediate nodes *
What we need to do now is to compare which route is shorter between the two routes , Take the short route as i reach j Route */ public void floyd() { int len;
// Length of storage path for (int k = 0; k < dis.length; k++) { for (int i = 0; i < dis.length;
i++) { for (int j = 0; j < dis.length; j++) { len = dis[i][k] + dis[k][j];
// This is i arrive earlier than k, Again j Route if (len < dis[i][j]) {
// If k A transit route for villages , Biyou i Directly to j The route is even shorter , Will be i reach j Change the route to the transit route dis[i][j] = len;
// meanwhile , originally j The precursor node is i of , Now it's only after transfer j, therefore j The precursor contact of should be changed to k pre[i][j] = pre[k][j]; } } } } }
}

Technology
Daily Recommendation