首页 > 最短路径
头像
mlpan
编辑于 2021-04-20 10:00
+ 关注

最短路径

最短路径

最短路径

一般最短路径两种处理方法,dfs与bfs

dfs解法

利用一个数组保存点的使用状态,遍历过的设置为true,没遍历的设置为false
对每一个点的边进行遍历,依次进行
以到达最后一个点作为结束,因为题目只让求到n节点(下标也就是n-1)的最短距离

注意:题目有个大坑,就是说可能有重复边。所以在构造边图的时候需要进行一个比较(dp[edge[0] - 1][edge[1] - 1] = Math.min(edge[2] , dp[edge[0] - 1][edge[1] - 1]);),则不是直接赋值(dp[edge[0] - 1][edge[1] - 1] = edge[2];)

private int min = Integer.MAX_VALUE;

    public int findShortestPath (int n, int m, int[][] graph) {
        int[][] dp = new int[n][n];
        for(int[] d : dp){
            Arrays.fill(d , Integer.MAX_VALUE);
        }
        // 构造图
        for(int[] edge : graph){
            dp[edge[0] - 1][edge[1] - 1] = Math.min(edge[2] , dp[edge[0] - 1][edge[1] - 1]);
        }
        boolean[] used = new boolean[n];
        used[0] = true;
        dfs(0 , n , 0 , dp , used);
        return min == Integer.MAX_VALUE ? -1 : min;
    }
    public void dfs(int curr ,int n , int dst ,  int[][] graph ,boolean[] used){
        if(curr == n - 1){
            min = Math.min(min , dst);
            return ;
        }
        for(int i = 0 ; i < n ; i ++){
            // 如果有边可达,并且该点还没被使用
            if(graph[curr][i] != Integer.MAX_VALUE && !used[i]){
                used[i] = true;
                dfs(i , n , dst + graph[curr][i] , graph , used);
                used[i] = false;
            }
        }
    }

bfs解法

借助一个辅助类,存储到dst节点的cost是多少

优先队列以花费从小到大的顺序进行排序

如果队列中dst到达了n-1,那么就找到了最小的花费的值

有边就加入边,因为队列会自己排序,所以每次poll的都是花费最小的

注意:题目有个大坑,就是说可能有重复边。所以在构造边图的时候需要进行一个比较(dp[edge[0] - 1][edge[1] - 1] = Math.min(edge[2] , dp[edge[0] - 1][edge[1] - 1]);),则不是直接赋值(dp[edge[0] - 1][edge[1] - 1] = edge[2];)

     public int findShortestPath (int n, int m, int[][] graph) {
        int[][] dp = new int[n][n];
        for(int[] d : dp){
            Arrays.fill(d , Integer.MAX_VALUE);
        }
        for(int[] edge : graph){
            dp[edge[0] - 1][edge[1] - 1] = Math.min(edge[2] , dp[edge[0] - 1][edge[1] - 1]);
        }
        //优先队列按照花费进行从小到大的排序
        PriorityQueue<CityInfo> queue = new PriorityQueue<CityInfo>((o1,o2) ->{return o1.cost - o2.cost;});
        queue.offer(new CityInfo(0, 0));
        while(!queue.isEmpty()){
            CityInfo info = queue.poll();
            //如果到达了终点,而queue.poll的就是花费最低的,那么就给其返回
            if(info.dst == n - 1){
                return info.cost;
            }
            //到达目前的该点到其他点的路线是否存在,如果存在,就加入到队列中
            for(int i = 0 ;i < n ;i++){
                if(dp[info.dst][i] != Integer.MAX_VALUE){
                    queue.offer(new CityInfo(i , dp[info.dst][i] + info.cost));
                }
            }
        }
        return -1;
    }
    class CityInfo{
        int dst;
        int cost;
        public CityInfo(int dst ,int cost){
            this.dst = dst;
            this.cost = cost;
        }
    }

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐