力扣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;}
}