华为oj题(考察最短路算法)

最终需要确定的是start-->end，比方说下面的例子，start就是ABCC，end就是CEFG，那么，ABCC到CEFG经过了CCEF，那么求解ABCC到CCEF，ABCC到CCEF经过了BCCE，所以这个顺序是反过来的，所以代码就要这么写temp = strArray[mid].substring(3)+temp;，相当于就是换成前插了

public class Floyd {
    public int[][] getGraphMatri(String[] strArr){
        int length = strArr.length;
        int[][] matr = new int[length][length];
        for (int i = 0 ; i < length ;i++){
            for (int j=0;j<length;j++){
                if(i==j){
                    matr[i][j] = -1;
                } else {
                    if(strArr[i].substring(1).equals(strArr[j].substring(0,3))){
                        matr[i][j] = 1;
                    }else {
                        matr[i][j]=-1;
                    }
                }
            }
        }
        return matr;
    }

    public int[][] getMaxPath(int[][] matrix){
        int len = matrix.length;
        int[][] path = new int[len][len];
        for(int i = 0 ; i < len ; i++){
            for (int j = 0 ; j <len ; j++){

                    path[i][j] = -1;
                }
        }
        for(int k = 0; k <len ; k++){
            for (int i =0 ; i<len ; i++){
                for (int j = 0 ; j<len ; j++){
                    if(matrix[i][k]!=-1&& matrix[k][j]!=-1){
                        if(matrix[i][k]+matrix[k][j]>matrix[i][j]){
                            matrix[i][j] = matrix[i][k]+matrix[k][j];
                            path[i][j] = k;
                        }
                    }
                }
            }
        }
        return path;
    }

    public int[] getMaxDistanc(int[][] matrix){
        int max = 0;
        int len = matrix.length;
        int[] resStore = new int[3];

        for (int i = 0 ; i <len ; i++){
            for (int j = 0; j <len ; j++){
                if(max < matrix[i][j]){
                    max = matrix[i][j];
                    resStore[0] = i;
                    resStore[1] = j;
                    resStore[2] = max;
                }
            }
        }
        int maxNum = 0 ;
        for(int i = 0 ; i<len;i++){
            for (int j = 0;j <len;j++){
                if(matrix[i][j] == max){
                    maxNum++;
                }
            }
        }
        if(maxNum > 1){
            System.out.println("There are same paths");
            return null;
        }
        if(max == 0){
            System.out.println("There are same paths");
            return null;
        }
        return resStore;
    }

    public String getMaxConnPath(String inputStr){
        String[] strArray = inputStr.split(" ");
        int[][] matrix = getGraphMatri(strArray);
        int[][] path = getMaxPath(matrix);
        int[] resultArr = getMaxDistanc(matrix);
        if(resultArr == null){
            return "There are same paths";

        }
        int start = resultArr[0];
        int end = resultArr[1];
        int mid = path[start][end];
        if(start==end){
            return "Error";
        }
        String temp = "";
        String result = strArray[start];
        while (mid!=-1){
            temp = strArray[mid].substring(3)+temp;
            mid = path[start][mid];
        }
        result =result+temp;
        result = result+strArray[end].substring(3);
        return result;
    }

    public static void main(String[] args) {
        Floyd f = new Floyd();
        String inputStr = "ABCC CEFG BCCE CCEF";
        System.out.println("The max path is:"+f.getMaxConnPath(inputStr));
    }
}

yooocen / dadaLearningBlogs

华为oj题(考察最短路算法) #20