java弗洛伊德算法(最短路径问题)

package com.csw.algorithm.floyd;

import sun.security.util.Length;

import java.util.Arrays;

/**
 * @Auther: 行路
 * @Date: Created on 2020/5/8 16:06 星期五
 * @Description: com.csw.algorithm.floyd
 * @version: 1.0 弗洛伊德算法
 */
public class FloydAlgorithm {
    public static void main(String[] args) {
        //测试图是否创建成功
        char[] vertex={'A','B','C','D','E','F','G'};
        //创建领接矩阵
        int[][] matrix=new int[vertex.length][vertex.length];
        final int N=65535;
        matrix[0] = new int[]{0, 5, 7, N, N, N, 2};
        matrix[1] = new int[]{5, 0, N, 9, N, N, 3};
        matrix[2] = new int[]{7, N, 0, N, 8, N, N};
        matrix[3] = new int[]{N, 9, N, 0, N, 4, N};
        matrix[4] = new int[]{N, N, 8, N, 0, 5, 4};
        matrix[5] = new int[]{N, N, N, 4, 5, 0, 6};
        matrix[6] = new int[]{2, 3, N, N, 4, 6, 0};

        //创建Graph对象
        Graph graph = new Graph(vertex.length, matrix, vertex);
        //调用弗洛伊德算法
        graph.floyd();
        graph.show();
    }
}

//创建图
class Graph {
    private char[] vertex; //存放顶点的数组
    private int[][] dis; //记录从各个顶点出发到其他顶点的距离,最后的结果,也是保留在该数组总
    private int[][] pre; //保存到达目标顶点的前驱节点



    /**
     *构造器
     * @param length  大小
     * @param matrix  领接矩阵
     * @param vertex  顶点数组
     */
    public Graph(int length,int[][] matrix,char[] vertex){
        this.vertex=vertex;
        this.dis=matrix;
        this.pre=new int[length][length];
        //对pre数组初始化,存放的是前驱节点的下标
        for(int i=0;i<length;i++){
            Arrays.fill(pre[i],i);
        }

    }

    //显示pre数组和dis数组
    public void show(){
        //为了显示便于阅读,优化输出
        for(int k=0;k<dis.length;k++){
            //先将pre数组输出一行数据
            for(int i=0;i<dis.length;i++){
                System.out.print(vertex[pre[k][i]]+" ");
            }
            System.out.println("");
            //输出dis数组的一行数据
            for(int i=0;i<dis.length;i++){
                System.out.print("("+vertex[k]+"到"+vertex[i]+"的最短路径"+dis[k][i]+") ");
            }
            System.out.println("");
            System.out.println("");
        }
    }

    //弗洛伊德算法
    public void floyd(){
        int len=0; //记录变量保存距离
        //中间顶点的遍历,k就是中间顶点的下标 ['A','B','C','D','E','F','G']
        for(int k=0;k<dis.length;k++){
            //从i顶点开始出发['A','B','C','D','E','F','G']
            for(int i=0;i<dis.length;i++){

                //j到达顶点 ['A','B','C','D','E','F','G']
                for(int j=0;j<dis.length;j++){
                    len=dis[i][k]+dis[k][j]; //从i顶点出发,经过k中间顶点,到达J顶点距离
                    if(len<dis[i][j]){
                        //如果len小于dis[i][j]
                        dis[i][j]=len; //更新距离
                        pre[i][j]=pre[k][j]; //更新前驱节点
                    }
                }
            }
        }
    }

}