java-floyd最短距离算法

╰半橙微兮° 2024-02-19 14:30 49阅读 0赞

java-floyd最短距离算法

public static void main (String[] args){
        MatrixDG matrixDG = new MatrixDG();
        System.out.println("初始化邻接矩阵");
        matrixDG.printMatrix();
        System.out.println("运行 floyd 算法");
        matrixDG.floyd();
        System.out.println("最终值");
        matrixDG.printMatrix();
    }
    public static class MatrixDG{
        private char[] mVexs=new char[]{'a','b','c','d'};//顶点集合
        private int[][] mMatrix;//邻接矩阵
        private int mnfinity=99;//表示无穷大
        //创建图，根据已有的数据
        public MatrixDG(){
            //初始化顶点边
            initEdge();
            //初始化边，及距离
            initEdgeSpace();
        }
    
        /**
            * floyd 佛洛伊德
            */
        private void floyd(){
            //输入顶点数和边数
            int n = mVexs.length;//vertex，顶点数
            int [][] e = mMatrix;
                //Floyd-Warshall算法核心语句（设k为中转节点，计算节点i到节点j的距离值）
                for(int k=0;k<n;k++) {
                    for (int i = 0; i < n; i++) {
                        for (int j = 0; j < n; j++) {
                            if (e[i][j] > e[i][k] + e[k][j]) {
                                e[i][j] = e[i][k] + e[k][j];
                            }
                        }
                    }
                }
        }
        private void initEdge(){
            //输入顶点数和边数
            int vlen = mVexs.length;//vertex，顶点数
            int elen = mVexs.length;//edge，边数
            //初始化边
            mMatrix = new int[vlen][elen];
            //初始化，使相同顶点距离为0，到其他订单距离为正无穷
            for(int i=0;i<vlen;i++){
                for(int j=0;j<elen;j++){
                    if(i==j){
                        mMatrix[i][j]=0;
                    }else{
                        mMatrix[i][j]=mnfinity;
                    }
                }
            }
        }
        //初始化，边及距离
        private void initEdgeSpace(){
            edgeSpace('a','b',2);
            edgeSpace('a','c',6);
            edgeSpace('a','d',4);
    
            edgeSpace('b','c',3);
    
            edgeSpace('c','a',7);
            edgeSpace('c','d',1);
    
            edgeSpace('d','a',5);
            edgeSpace('d','c',12);
        }
    
        /**
            *
            * @param e1 边
            * @param e2 边
            * @param space 距离
            */
        private void edgeSpace(char e1,char e2,int space){
            int i= getPosition(e1);
            int j= getPosition(e2);
            mMatrix[i][j]=space;
        }
        //获取字符在数组中的位置
        private int getPosition(char ch){
            for(int i=0;i<mVexs.length;i++){
                if(mVexs[i] == ch)
                    return i;
            }
            return -1;
        }
    
        //打印邻接矩阵
        private void printMatrix(){
            //顶点
            for(int i=0;i<mVexs.length;i++){
                if(i==0) {
                    System.out.print("\t");
                }
                System.out.print(mVexs[i] + "\t");
            }
            System.out.println();
            //顶点的邻接表
            for(int i=0;i<mVexs.length;i++){
                System.out.print(mVexs[i] + "\t");
                for(int j=0;j<mVexs.length;j++) {
                    System.out.print(mMatrix[i][j] + "\t");
                }
                System.out.println();
            }
        }
    }