代码如下:

public class Test {
    /**
     * 采用Floyd算法(动态规划思想):两点A,B之间的最短距离可以看成A->K和K->B的各自最短距离之和
     * 时间复杂度为O(n^3),复杂度较高,但是实现简单,核心代码只有几行
     * @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);

        // 核心代码
        // 取k节点,使得i到k和k到j的距离最短
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i!=j && arcs[i][k] < Integer.MAX_VALUE && arcs[k][j] < Integer.MAX_VALUE) {
                        final int d = arcs[i][k] + arcs[k][j];
                        if (d < arcs[i][j]) { //经过k点时i到j的距离比不经过k点的距离更短
                            arcs[i][j] = d; //更新i到j的最短距离
                            arcs[j][i] = d;
                        }
                    }
                }
            }
        }
        print(arcs);

        return arcs[start-1][end-1]==Integer.MAX_VALUE?-1:arcs[start-1][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号