<>介绍

<>算法分析

1、设置顶点vi到vk的最短路径已知为Lik,顶点vk到vj的最短路径为Lkj,顶点vi到vj的路径为Lij，则vi到vj的最短路径为：min(Lik+Lkj)，vk的取值为所有顶点，则可获得vi到vj的最短路径。
2、至于vi到vk的最短路径Lik或者vk到vj的最短路径Lkj，是以同样的方式获得。

<>算法应用

package algorithm; import java.util.Arrays; /** * @author taoke * @desc 弗洛伊德算法
* @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 { /** * 顶点 */ private final char[] vertex; /** *

private final int[][] pre; /** * 初始化 * * @param length 顶点长度大小 * @param matrix

length) { this.vertex = vertex; this.matrix = matrix; this.pre = new
int[length][length]; //对pre数组初始化，存放的是前驱顶点的下标 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(); } } /** * 弗洛伊德算法 */ public void floyd() { int
len;//变量保存距离 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;//更新距离 pre[j][k] = pre[i][k];//更新前驱节点 } } } } } } }
<>结果

GitHub

Gitee