java-floyd最短距离算法

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();
        }
    }
}