Algorithme Floyd: utilisé pour résoudre le chemin le plus court de la multi-source et calcule la distance la plus courte entre tous les nœuds et les nœuds restants.
L'idée de cet algorithme est: d'abord initialiser la matrice de distance, puis mettre à jour progressivement la valeur du point de la matrice à partir du premier point. D [i] [J] représente la distance du point I au point j. Lorsque les k mettent les mises à jour, jugez les tailles de d [i] [k] + d [k] [j] et d [i] [j]. Si le premier est petit, mettez à jour cette valeur, sinon elle ne changera pas.
Donnez un exemple:
L'algorithme de mise en œuvre de Floyd spécifique est le suivant [Java] Afficher la copie simple
Package Com.Blyang; classe publique floyd {int [] [] matrice; nœuds char []; private final int inf = Integer.max_value; public floyd (char [] nœuds, int [] [] matrice) {this.nodes = nœuds; this.matrix = matrix; } public void floyd () {int [] [] distance = new int [nœuds.length] [nœuds.length]; // initialise la matrice de distance pour (int i = 0; i <nœuds.length; i ++) {for (int j = 0; j <nœuds.length; j ++) {distance [i] [j] = matrice [i] [j]; }} // Loop Mettez à jour la valeur de la matrice pour (int k = 0; k <nœuds.length; k ++) {for (int i = 0; i <nœuds.length; i ++) {for (int j = 0; j <nœuds.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; }}}}} // Imprimez le résultat du Path System le plus court de Floyd.out.printf ("floyd: / n"); pour (int i = 0; i <nœuds.length; i ++) {pour (int j = 0; j <nœuds.length; j ++) System.out.printf ("% 12d", distance [i] [j]); System.out.printf ("/ n"); }}} Après la mise en œuvre, un test est donné pour les points et les poids de la figure ci-dessus:
Package Com.Blyang; classe publique Main {public static void main (String [] args) {int inf = Integer.max_value; char [] nœuds = {'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 [nœuds.length]; Floyd floyd = nouveau floyd (nœuds, matrice); floyd.floyd (); }}Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.