Algoritmo Floyd: se usa para resolver la ruta más corta de la fuente múltiple y calcula la distancia más corta entre todos los nodos y los nodos restantes.
La idea de este algoritmo es: Primero inicialice la matriz de distancia y luego actualice gradualmente el valor del punto de la matriz a partir del primer punto. D [i] [j] representa la distancia desde el punto I hasta el punto j. Cuando se actualice K, juzga los tamaños de D [i] [k]+d [k] [j] y d [i] [j]. Si el primero es pequeño, actualice este valor, de lo contrario no cambiará.
Dar un ejemplo:
El algoritmo específico de implementación de Floyd es el siguiente [Java] Ver copia simple
paquete com.blyang; public class Floyd {int [] [] matrix; Char [] nodos; Private final int inf = integer.max_value; public floyd (char [] nodos, int [] [] matrix) {this.nodes = nodos; this.matrix = matrix; } public void floyd () {int [] [] distancia = new int [nodo.length] [nodo.length]; // Inicializar la matriz de distancia para (int i = 0; i <nodo.length; i ++) {for (int j = 0; j <nodes.length; j ++) {distancia [i] [j] = matrix [i] [j]; }} // Actualizar el valor de la matriz para (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 = (distancia [i] [k] == Inf || Distancia [k] [j] == Inf)? Inf: distancia [i] [k] + distancia [k] [j]; if (distancia [i] [j]> temp) {distancia [i] [j] = temp; }}}}} // Imprima el resultado de la ruta más corta de Floyd System.out.printf ("Floyd: /n"); for (int i = 0; i <nodo.length; i ++) {for (int j = 0; j <nodo.length; j ++) system.out.printf ("%12d", distancia [i] [j]); System.out.printf ("/n"); }}} Después de la implementación, se da una prueba para los puntos y pesos de la figura anterior:
paquete com.blyang; clase pública Main {public static void main (string [] args) {int inf = integer.max_value; char [] nodos = {'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 [nodo.length]; Floyd Floyd = New Floyd (nodos, matriz); floyd.floyd (); }}Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.