力扣labuladong一刷day49天迪杰斯特拉

力扣labuladong一刷day49天迪杰斯特拉

一、743. 网络延迟时间

题目链接：https://leetcode.cn/problems/network-delay-time/
使用迪杰斯特拉解决加权图某点到所有节点距离的问题。
如果是无权图，采用广度优先遍历即可，就把图想象成一颗树，广度优先就可以说是层序遍历。
而加权图寻找最短距离，最经典算法就是迪杰斯特拉算法，我们可以计算出某一个点到任意一个之间的最短距离。我们采用优先级队列，里面的每一个元素记录的是某点到起点之间的最短距离，我们会一直按照最短距离更新，这样到达结尾后即可得到最短距离。

class Solution {
     public int networkDelayTime(int[][] times, int n, int k) {
        List<int[]>[] graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] time : times) {
            int a = time[0], b = time[1], c = time[2];
            graph[a].add(new int[]{b, c});
        }
        int[] dist = djk(k, graph);
        int res = -1;
        for (int i = 1; i < dist.length; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            res = Math.max(res, dist[i]);
        }
        return res;
    }

    class State {
        int id;
        int sToMe;
        public State(int id, int sToMe) {
            this.id = id;
            this.sToMe = sToMe;
        }
    }

    int[] djk(int start, List<int[]>[] graph) {
        int[] dist = new int[graph.length];
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<State> pq = new PriorityQueue<>((a, b) -> a.sToMe - b.sToMe);

        dist[start] = 0;
        pq.add(new State(start, 0));
        while (!pq.isEmpty()) {
            State poll = pq.poll();
            int id = poll.id;
            int cur = poll.sToMe;

            if (cur > dist[id]) continue;
            for (int[] ints : graph[id]) {
                int nextId = ints[0];
                int temp = dist[id] + ints[1];
                if (temp < dist[nextId]) {
                    dist[nextId] = temp;
                    pq.add(new State(nextId, temp));
                }
            }
        }
        return dist;
    }
}

二、1631. 最小体力消耗路径

题目链接：https://leetcode.cn/problems/path-with-minimum-effort/
思路：基本上就是迪杰斯特拉的典型题目，只不过这一次求的是最小消耗，但我们在过程中需要求每一条路径的最大消耗，在去往下一个点时选择这些最大消耗中的最小消耗，做为路径的延伸。

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int r = heights.length, c = heights[0].length;
        return djk(heights);
    }
    List<int[]> getList(int x, int y, int r, int c) {
        int[][] temp = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        List<int[]> list = new ArrayList<>();
        for (int[] ints : temp) {
            int nx = x + ints[0], ny = y + ints[1];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            list.add(new int[] {nx, ny});
        }
        return list;
    }
    class State {
        int x;
        int y;
        int sToMe;
        public State(int x, int y, int sToMe) {
            this.x = x;
            this.y = y;
            this.sToMe = sToMe;
        }
    }

    int djk(int[][] heights) {
        int r = heights.length, c = heights[0].length;
        int[][] dist = new int[r][c];
        PriorityQueue<State> pq = new PriorityQueue<>((a, b)-> a.sToMe - b.sToMe);
        for (int i = 0; i < r; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        pq.add(new State(0, 0, 0));
        dist[0][0] = 0;
        while (!pq.isEmpty()) {
            State poll = pq.poll();
            int x = poll.x, y = poll.y;
            int cur = poll.sToMe;
            if (x == r-1 && y == c-1) return cur;
            if (cur > dist[x][y]) continue;
            for (int[] ints : getList(x, y, r, c)) {
                int nLen =  Math.max(dist[x][y], Math.abs(heights[x][y]-heights[ints[0]][ints[1]]));
                if (nLen < dist[ints[0]][ints[1]]) {
                    dist[ints[0]][ints[1]] = nLen;
                    pq.add(new State(ints[0], ints[1], nLen));
                }
            }
        }
        return -1;
    }
}

三、1514. 概率最大的路径

题目链接：https://leetcode.cn/problems/path-with-maximum-probability/
思路：这题和上一题又有点不一样，相当于求最长路径，那么需要把优先级队列按照从大到小排序即可。

class Solution {
   public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        List<double[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < edges.length; i++) {
            int from = edges[i][0], to = edges[i][1];
            graph[from].add(new double[]{to, succProb[i]});
            graph[to].add(new double[]{from, succProb[i]});
        }
        return djk(graph, start_node, end_node);
    }

    class State{
        int id;
        double sToE;
        public State(int id, double sToE) {
            this.id = id;
            this.sToE = sToE;
        }
    }
    double djk(List<double[]>[] graph, int s, int e) {
        double[] dist = new double[graph.length];
        PriorityQueue<State> pq = new PriorityQueue<>((a, b)->Double.compare(b.sToE, a.sToE));
        Arrays.fill(dist, -1);
        dist[s] = 1;
        pq.add(new State(s, 1));
        while (!pq.isEmpty()) {
            State poll = pq.poll();
            int id = poll.id;
            double cur = poll.sToE;

            if (id == e) return cur;
            if (cur < dist[id]) continue;

            for (double[] ints : graph[id]) {
                int to = (int) ints[0];
                double nLen = cur * ints[1];
                if (nLen > dist[to]) {
                    dist[to] = nLen;
                    pq.add(new State(to, nLen));
                }
            }
        }
        return 0.0;
    }
}