关于弗洛伊德算法求最短路径详解

　　public class Test1 {

　　public static void main(String[] args) {

　　System.out.println("请输入有几个顶点：");

　　Scanner scanner = new Scanner(System.in);

　　int n = scanner.nextInt();

　　char[] vertex = new char[n];

　　System.out.println("请输入各个顶点的符号，每个字符用空格分隔：");

　　for (int i = 0; i < n; i++) {

　　vertex[i] = scanner.next().charAt(0);

　　}

　　int[][] arr = new int[n][n];

　　System.out.println("请输入各个顶点在二维表之间的距离，不能直达的用100表示：");

　　for (int i = 0; i < n; i++) {

　　for (int j = 0; j < n; j++) {

　　arr[i][j] = scanner.nextInt();

　　}

　　}

　　Graph gp = new Graph(vertex, arr, n);

　　gp.floyd();

　　gp.show(vertex);

　　}

　　}

　　//创建图

　　class Graph {

　　private char[] vertex;

　　private int[][] dis; // 从顶点出发到其他节点的距离

　　private int[][] pre; // 目标节点的前驱节点

　　// 顶点数组 邻接矩阵 长度大小

　　public Graph(char[] vertex, int[][] dis, int len) {

　　this.vertex = vertex;

　　this.dis = dis;

　　this.pre = new int[len][len];

　　// 对pre数组进行初始化

　　for (int i = 0; i < len; i++) {

　　Arrays.fill(pre[i], i);

　　}

　　}

　　public void show(char[] vertex) {

　　for (int i = 0; i < dis.length; i++) {

　　for (int j = 0; j < dis.length; j++) {

　　System.out.print(vertex[pre[i][j]] + " ");

　　}

　　System.out.println();

　　for (int j = 0; j < dis.length; j++) {

　　System.out.print("( " + vertex[i] + " -> " + vertex[j] + " 的最短路径 " + dis[i][j] + " ) ");

　　}

　　System.out.println();

　　}

　　}

　　// 弗洛伊德算法

　　public void floyd() {

　　int len = 0;

　　// 从中间节点进行遍历

　　for (int k = 0; k < dis.length; k++) {

　　// 对出发节点进行遍历

　　for (int i = 0; i < dis.length; i++) {

　　// 遍历终点节点

　　for (int j = 0; j < dis.length; j++) {

　　len = dis[i][k] + dis[k][j];

　　if (len < dis[i][j]) {

　　dis[i][j] = len;

　　pre[i][j] = pre[k][j];

　　}

　　}

　　}

　　}

　　}

　　}