public class Test {
    /**
     * 采用Dijkstra算法:
     * 从起始点开始遍历,将遍历后的最小值确定下来,然后将剩下的节点继续遍历,每次都更新最小值
     * 时间复杂度为O(n^2),基本满足日常使用,如还需优化,可采用邻接表+优先队列进行优化
     * @param n 定点个数
     * @param edges 二维数组,边的权重
     *              例如:{{1,2,1},{2,3,3},{1,3,100}}
     *              点1到点2的边权值是1
     *              点2到点3的边权值是3
     *              点1到点3的边权值是100
     *              转化后成邻接矩阵可得到
     *              0    1   100
     *              1    0   3
     *              100  3   0
     * @param start 起始点
     * @param end   结束点
     * @return 返回起始点到结束点的最短距离
     */
    int minPath(int n, int[][] edges, int start, int end){
        // 构建邻接矩阵
        int[][] arcs = new int[n][n];
        Arrays.stream(arcs).forEach(e->Arrays.fill(e,Integer.MAX_VALUE));
        for (int[] edge : edges) {
            arcs[edge[0] - 1][edge[1] - 1] = edge[2];
            arcs[edge[1] - 1][edge[0] - 1] = edge[2];
        }
        print(arcs);

        // 创建变量及数组
        int[] minValue=new int[n]; // 保存最小值
        boolean[] finished=new boolean[n]; // 保存是否完成
        int finishedSize=0; // 保存最小值和最小值的索引
        int minIndex=0; // 保存下一个起始点
        int min=Integer.MAX_VALUE; // 保存每次遍历的最小值

        // 数据初始化
        Arrays.fill(minValue,Integer.MAX_VALUE);
        minValue[start-1]=0;
        finished[start-1]=true;
        finishedSize++;
        int index=start-1;

        // 主要代码
        for (int j=0;j<arcs.length;j++){
            if(finishedSize==n){
                break;
            }
            for (int i=0;i<finished.length;i++){
                if(!finished[i] && arcs[index][i]!=Integer.MAX_VALUE){ // 如果未标记 且 连通
                    // 起始点到上一个点的最小值|该点的权值 < 起始点到该点最小值,则更新
                    if((minValue[index]|arcs[index][i])<minValue[i]){
                        minValue[i]=(minValue[index]|arcs[index][i]);
                        // 记录最小值
                        if(minValue[i]<min){
                            min=minValue[i];
                            minIndex=i;
                        }
                    }
                }
            }

            finished[minIndex]=true; // 标记已经确定的最小值的点
            finishedSize++;
            index=minIndex; // 将最小值点设置为起始点
            min=Integer.MAX_VALUE;
        }
        System.out.println(Arrays.toString(minValue));

        return minValue[end-1]==Integer.MAX_VALUE?-1:minValue[end-1];
    }

    // 打印二维数组
    void print(int[][] view){
        for (int i=0;i<view.length;i++){
            for(int j=0;j<view[i].length;j++){
                if(view[i][j]==Integer.MAX_VALUE){
                    System.out.print("∞\t");
                }else{
                    System.out.print(view[i][j]+"\t");
                }
            }
            System.out.println();
        }
        System.out.println("===============");
    }

    public static void main(String[] args) {
        int[][] edges = new int[][]{{1,2,1},{2,3,3},{1,3,100}};
        int i = new Test().minPath(3, edges, 1, 3);
        System.out.println(i);
    }
}
0条评论
头像
ICP证 : 浙ICP备18021271号