黑马程序员技术交流社区

标题: 【上海校区】最短路径问题 [打印本页]

---

作者: 梦缠绕的时候    时间: 2018-11-26 09:38
标题: 【上海校区】最短路径问题
问题：

*光明小学的小朋友们要举行一年一度的接力跑大赛了，但是小朋友们却遇到了一个难题：设计接力跑大赛的线路，你能帮助他们完成这项工作么？
*光明小学可以抽象成一张有N个节点的图，每两点间都有一条道路相连。光明小学的每个班都有M个学生，所以你要为他们设计出一条恰好经过M条边的路径。
*光明小学的小朋友们希望全盘考虑所有的因素，所以你需要把任意两点间经过M条边的最短路径的距离输出出来以供参考。
*
*你需要设计这样一个函数：
*res[][] Solve( N, M, map[][]);
*注意：map必然是N * N的二维数组，且map[j] == map[j]，map == 0，-1e8 <= map[j] <= 1e8。
*（道路全部是无向边，无自环）2 <= N <= 100, 2 <= M <= 1e6。
*
*map数组表示了一张稠密图，其中任意两个不同节点i,j间都有一条边，边的长度为map[j]。N表示其中的节点数。
*你要返回的数组也必然是一个N * N的二维数组，表示从i出发走到j，经过M条边的最短路径
*你的路径中应考虑包含重复边的情况。

输入输出样例：

输入样例：

3
2
3 3
0 2 3
2 0 1
3 1 0

输出样例：

[[4, 4, 3],

[4, 2, 5],

[3, 5, 2]]

样例解释：



代码：


public class Main {
       
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                //图的路径权重
                int[][] arr = {{0,2,3},
                                           {2,0,1},
                                           {3,1,0}};
                //人的个数（图变为树的尝试）
                int m = 2;
                //结点数
                int n = 3;
                //暂时保存路径用
                int[] path = new int[n+1];
                path[0] = n;
                int[][] res = new int[3][3];//用于保存结果
                for(int i=0; i<res.length; i++){
                        for(int j=0; j<res[0].length; j++){
                                res[j] = Integer.MAX_VALUE;
                        }
                }
                //具体方法
                solve(n,m,1,arr,res,3,path);
                //输出结果
                for(int i=0; i<res.length; i++){
                        for(int j=0; j<res[0].length; j++){
                                System.out.print(res[j]);
                        }
                        System.out.println();
                }
        }
       
        public static void solve(int n, int m, int layer, int[][] arr, int[][] res, int root, int[] path){
                //已经找到最后一个结点
                if(layer == (m+2)){
                        int sum = 0;
                        //当前路径权重总和
                        for(int i=1; i<path.length-1; i++){
                                sum += arr[path][path[i+1]];
                        }
                        //若当前总和比最后结果中的还小，则替换
                        if(sum < res[path[1]][path[m+1]]){
                                res[path[1]][path[m+1]] = sum;
                        }
                }else{
                        //第一次有3(n)个结点
                        //之后有n-1个结点，代表上个结点可到达的结点（除去本身）
                        int[] subNodes = find(n,root);
                        for(int i=0; i<subNodes.length; i++){
                                //遍历可能到的结点
                                path[layer] = subNodes;
                                //递归进入下一个过程，找出subNodes可到达的结点
                                solve(n, m, layer+1, arr, res, subNodes, path);
                        }
                }
        }
       
        public static int[] find(int n, int root){
                //第一次返回图的所有结点
                if(n == root){
                        int[] temp = new int[n];
                        for(int i=0; i<n; i++){
                                temp = i;
                        }
                        return temp;
                }else{
                        //之后返回除本身外的节点
                        int[] temp = new int[n-1];
                        int t = 0;
                        for(int i=0; i<n; i++){
                                if(i == root){
                                        continue;
                                }
                                temp[t] = i;
                                t++;
                        }
                        return temp;
                }
        }
}
输出：


---------------------
作者：另一个我竟然存在
来源：CSDN
原文：https://blog.csdn.net/qq_24034545/article/details/82589083
版权声明：本文为博主原创文章，转载请附上博文链接！

---

作者: 不二晨    时间: 2018-11-28 15:46
奈斯

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2