- 2022-01-28 10:19
*views 4*- graph theory
- data structure
- algorithm

<> 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

- Java242 blogs
- Python241 blogs
- Vue112 blogs
- algorithm96 blogs
- c language93 blogs
- Flow Chart81 blogs
- MySQL71 blogs
- C++64 blogs
- more...

Daily Recommendation

© ioDraw All rights reserved

Linux shell Summary of script exercises windows And network foundation Outsourcing for five years , Abandoned ... computer network - Agreement and hierarchy The 11th Blue Bridge Cup was postponed — Mental journey and withdrawal Java Multithreading series — Implementation of multithreading (01)C language --- Simple Gobang games JAVA realization QQ Sign in , Registration and other functions 1060 graphics support dx12 Do you _1050Ti Or add some money 1060, You'll know after reading it Wu Enda machine learning - Detect exception server