zcq
    Floyd算法解决最短路径问题。

    1. package com.atguigu.floyd;
    3. import java.util.Arrays;
    5. public class FloydAlgorithm {
    7.     public static void main(String[] args) {
    8.         // 测试看看图是否创建成功
    9.         char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
    10.         //创建邻接矩阵
    11.         int[][] matrix = new int[vertex.length][vertex.length];
    12.         final int N = 65535;
    13.         matrix[0] = new int[] { 0, 5, 7, N, N, N, 2 };
    14.         matrix[1] = new int[] { 5, 0, N, 9, N, N, 3 };
    15.         matrix[2] = new int[] { 7, N, 0, N, 8, N, N };
    16.         matrix[3] = new int[] { N, 9, N, 0, N, 4, N };
    17.         matrix[4] = new int[] { N, N, 8, N, 0, 5, 4 };
    18.         matrix[5] = new int[] { N, N, N, 4, 5, 0, 6 };
    19.         matrix[6] = new int[] { 2, 3, N, N, 4, 6, 0 };
    21.         //创建 Graph 对象
    22.         Graph graph = new Graph(vertex.length, matrix, vertex);
    23.         //调用弗洛伊德算法
    24.         graph.floyd();
    25.         graph.show();
    26.     }
    28. }
    30. // 创建图
    31. class Graph {
    32.     private char[] vertex; // 存放顶点的数组
    33.     private int[][] dis; // 保存，从各个顶点出发到其它顶点的距离，最后的结果，也是保留在该数组
    34.     private int[][] pre;// 保存到达目标顶点的前驱顶点
    36.     // 构造器
    37.     /**
    38.      * 
    39.      * @param length
    40.      *            大小
    41.      * @param matrix
    42.      *            邻接矩阵
    43.      * @param vertex
    44.      *            顶点数组
    45.      */
    46.     public Graph(int length, int[][] matrix, char[] vertex) {
    47.         this.vertex = vertex;
    48.         this.dis = matrix;
    49.         this.pre = new int[length][length];
    50.         // 对pre数组初始化, 注意存放的是前驱顶点的下标
    51.         for (int i = 0; i < length; i++) {
    52.             Arrays.fill(pre[i], i);
    53.         }
    54.     }
    56.     // 显示pre数组和dis数组
    57.     public void show() {
    59.         //为了显示便于阅读，我们优化一下输出
    60.         char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
    61.         for (int k = 0; k < dis.length; k++) {
    62.             // 先将pre数组输出的一行
    63.             for (int i = 0; i < dis.length; i++) {
    64.                 System.out.print(vertex[pre[k][i]] + " ");
    65.             }
    66.             System.out.println();
    67.             // 输出dis数组的一行数据
    68.             for (int i = 0; i < dis.length; i++) {
    69.                 System.out.print("("+vertex[k]+"到"+vertex[i]+"的最短路径是" + dis[k][i] + ") ");
    70.             }
    71.             System.out.println();
    72.             System.out.println();
    74.         }
    76.     }
    78.     //弗洛伊德算法, 比较容易理解，而且容易实现
    79.     public void floyd() {
    80.         int len = 0; //变量保存距离
    81.         //对中间顶点遍历， k 就是中间顶点的下标 [A, B, C, D, E, F, G] 
    82.         for(int k = 0; k < dis.length; k++) { // 
    83.             //从i顶点开始出发 [A, B, C, D, E, F, G]
    84.             for(int i = 0; i < dis.length; i++) {
    85.                 //到达j顶点 // [A, B, C, D, E, F, G]
    86.                 for(int j = 0; j < dis.length; j++) {
    87.                     len = dis[i][k] + dis[k][j];// => 求出从i 顶点出发，经过 k中间顶点，到达 j 顶点距离
    88.                     if(len < dis[i][j]) {//如果len小于 dis[i][j]
    89.                         dis[i][j] = len;//更新距离
    90.                         pre[i][j] = pre[k][j];//更新前驱顶点
    91.                     }
    92.                 }
    93.             }
    94.         }
    95.     }
    96. }