Floyd algorithm: used to solve the shortest path of multi-source, and calculates the shortest distance between all nodes and the remaining nodes.
The idea of this algorithm is: first initialize the distance matrix, and then gradually update the matrix point value starting from the first point. d[i][j] represents the distance from point i to point j. When the k updates, judge the sizes of d[i][k]+d[k][j] and d[i][j]. If the former is small, update this value, otherwise it will not change.
Give an example:
The specific floyd implementation algorithm is as follows [java] view plain copy
package com.blyang; public class Floyd { int[][] Matrix; char[] Nodes; private final int INF = Integer.MAX_VALUE; public Floyd(char[] Nodes, int[][] Matrix){ this.Nodes = Nodes; this.Matrix = Matrix; } public void floyd(){ int[][] distance = new int[Nodes.length][Nodes.length]; // Initialize the distance matrix for(int i=0; i<Nodes.length; i++){ for(int j=0; j<Nodes.length; j++){ distance[i][j] = Matrix[i][j]; } } //Loop update the value of the matrix for(int k=0; k<Nodes.length; k++){ for(int i=0; i<Nodes.length; i++){ for(int j=0; j<Nodes.length; j++){ int temp = (distance[i][k] == INF || distance[k][j] == INF) ? INF : distance[i][k] + distance[k][j]; if(distance[i][j] > temp){ distance[i][j] = temp; } } } } } // Print the result of floyd's shortest path System.out.printf("floyd: /n"); for (int i = 0; i < Nodes.length; i++) { for (int j = 0; j < Nodes.length; j++) System.out.printf("%12d", distance[i][j]); System.out.printf("/n"); } } } After implementation, a test is given for the points and weights of the figure above:
package com.blyang; public class Main { public static void main(String[] args) { int INF = Integer.MAX_VALUE; char[] Nodes = {'0', '1', '2', '3'}; int matrix[][] = { /*A*//*B*//*C*//*D*/ /*A*/ { 0, 1, 2, 1}, /*B*/ { INF, 0, INF, INF}, /*C*/ { INF, 3, 0, 1}, /*D*/ { INF, 1, 1, 0}, }; int[] dist = new int[Nodes.length]; Floyd floyd = new Floyd(Nodes, matrix); floyd.floyd(); } }The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.