最短路径

一般最短路径两种处理方法，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;
        }
    }