单源最短路径【学习算法】

前言

2023-8-14 18:21:41

以下内容源自《【学习算法】》
仅供学习交流使用

版权

禁止其他平台发布时删除以下此话
本文首次发布于CSDN平台
作者是CSDN@日星月云
博客主页是https://blog.csdn.net/qq_51625007
禁止其他平台发布时删除以上此话

推荐

第七章 图【数据结构与算法】

单源最短路径

Java算法实现

代码

import java.util.*;/*** 在这个代码模板中，我们通过遍历int[] paths来构建图的邻接表。* 每个元素paths[i]表示从顶点paths[i][0]到顶点paths[i][1]的距离为paths[i][2]。** 我们使用一个ArrayList来表示图的邻接表，每个顶点都有一个对应的列表，其中存储了与该顶点相连的边的目标顶点及其权重。** 然后，我们可以使用Dijkstra算法来计算从给定起始顶点到其他顶点的最短距离。* 算法的时间复杂度为O((V+E)logV)，其中V为顶点的数量，E为边的数量。** 这个代码模板使用了优先队列来实现最小堆，以提高算法的效率。算法的时间复杂度为O(ElogV)，其中E为边的数量，V为顶点的数量。*/
public class Dijkstra {public static void main(String[] args) {//int[][] paths = {{0, 1, 2}, {0, 2, 4}, {1, 2, 1}, {1, 3, 4}, {1, 4, 2}, {2, 4, 3}, {3, 5, 2}, {4, 3, 3}, {4, 5, 2}};int n = 6;int[] dist = dijkstra(paths, n, 0);System.out.println(Arrays.toString(dist));int distD = dijkstraD(paths, n, 0,n-1);System.out.println(distD);}public static int[] dijkstra(int[][] paths, int n, int start) {//邻接表List<int[]>[] graph = new ArrayList[n];//初始化for (int i = 0; i < n; i++) {graph[i] = new ArrayList<>();}//初始化for (int[] path : paths) {int source = path[0];int destination = path[1];int weight = path[2];graph[source].add(new int[]{destination, weight});graph[destination].add(new int[]{source, weight});}//距离int[] dist = new int[n];Arrays.fill(dist, Integer.MAX_VALUE);dist[start] = 0;//优先队列PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);//表示到达顶点 最小距离pq.offer(new int[]{start, 0});while (!pq.isEmpty()) {//取出int[] curr = pq.poll();int vertex = curr[0];int distance = curr[1];//跳过if (distance > dist[vertex]) {continue;}//更新for (int[] edge : graph[vertex]) {int newDistance = distance + edge[1];if (newDistance < dist[edge[0]]) {dist[edge[0]] = newDistance;pq.offer(new int[]{edge[0], newDistance});}}}return dist;}public static int dijkstraD(int[][] paths,int n, int start,int end) {//邻接表List<int[]>[] graph = new ArrayList[n];//初始化for (int i = 0; i < n; i++) {graph[i] = new ArrayList<>();}//初始化for (int[] path : paths) {int source = path[0];int destination = path[1];int weight = path[2];graph[source].add(new int[]{destination, weight});graph[destination].add(new int[]{source, weight});}//距离int[] dist = new int[n];Arrays.fill(dist, Integer.MAX_VALUE);dist[start] = 0;//优先队列PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);//表示到达顶点 最小距离pq.offer(new int[]{start, 0});while (!pq.isEmpty()) {int[] curr = pq.poll();int vertex = curr[0];int distance = curr[1];if (distance > dist[vertex]) {continue;}if (vertex==end){return distance;}for (int[] edge : graph[vertex]) {int newDistance = distance + edge[1];if (newDistance < dist[edge[0]]) {dist[edge[0]] = newDistance;pq.offer(new int[]{edge[0], newDistance});}}}return dist[end];}
}

结果

[0, 2, 3, 6, 4, 6]
6

带限制的单源最短路径

1928. 规定时间内到达终点的最小花费

1928. 规定时间内到达终点的最小花费

class Solution {/*带限制的最短路径操作其实就是最短路径算法的变化版本，这里带限制的条件使得我们在向对应的队列加入元素的时候需要进行一定的判断，只有能够帮助我们的答案达到更优的操作才能够加入到队列当中，否则就会由于加入过多的元素导致最终超时。作者：豆小科链接：https://leetcode.cn/problems/minimum-cost-to-reach-destination-in-time/solutions/2224593/dai-xian-zhi-de-zui-duan-lu-jing-cao-zuo-d7t6/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/public static int minCost(int maxTime, int[][] edges, int[] passingFees) {// 使用最短路径进行处理int n = passingFees.length;//构造图邻接表List<List<int[]>> graph = new ArrayList<>();for (int i = 0; i < n; i++) graph.add(new ArrayList<>());for (int[] edge : edges) {int x = edge[0];int y = edge[1];int time = edge[2];graph.get(x).add(new int[]{y, time});graph.get(y).add(new int[]{x, time});}//优先队列PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));//时间 花费 当前结点queue.add(new int[]{0, passingFees[0], 0});//到达node的最少时间Map<Integer, Integer> timeMap = new HashMap<>();while (!queue.isEmpty()) {int[] poll = queue.poll();int time = poll[0];int ct = poll[1];int node = poll[2];//继续if (time > maxTime) continue;//结束if (node == n - 1) return ct;//更新if (!timeMap.containsKey(node) || timeMap.get(node) > time) {timeMap.put(node, time);for (int[] e : graph.get(node)) {queue.add(new int[]{e[1] + time, passingFees[e[0]] + ct, e[0]});}}}return -1;}
}

LCP 35. 电动车游城市

LCP 35. 电动车游城市

    /*** 首先建图， 存储每个城市相邻的城市和距离** 使用一个二维数组保存结果arr[i][j] = k， i = 所在城市， j = 剩余电量， k = 最短时间** 用队列来记录每个路径的信息 {time,cur,power}， time = 已用时间， cur = 所在城市， power = 剩余电量 (使用优先队列来保证每次优先执行已用时间最少的路径)** 每次只会有两种操作** 充一次电 - 新时间 = 已用时间 + 当前城市每单位充电需要时间， 新电量 = 剩余电量 + 1* 去往下一个城市 - 新时间 = 已用时间 + 去往该需要消耗的时间， 新电量 = 剩余电量 − 去往该城市需要消耗的电量** 作者：Feilulue 🍒* 链接：https://leetcode.cn/problems/DFPeFJ/solutions/974051/java-dijkstra-by-feilue-8p14/* 来源：力扣（LeetCode）* 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
class Solution {public int electricCarPlan(int[][] paths, int cnt, int start, int end, int[] charge) {int n = charge.length;//构造了图List<int[]>[] map = new List[n];for(int i = 0; i < n; i++) map[i] = new ArrayList();for(int[] path : paths){map[path[0]].add(new int[]{path[1], path[2]});map[path[1]].add(new int[]{path[0], path[2]});}//使用一个二维数组保存结果arr[i][j] = k//i = 所在城市， j = 剩余电量， k = 最短时间int[][] res = new int[n][cnt+1];for(int[] i : res) Arrays.fill(i, Integer.MAX_VALUE/2);res[start][0] = 0;//用队列来记录每个路径的信息 {time,cur,power}，//time = 已用时间， cur = 所在城市， power = 剩余电量//(使用优先队列来保证每次优先执行已用时间最少的路径)Queue<int[]> queue = new PriorityQueue<int[]>((x, y) -> (x[0] - y[0]));queue.offer(new int[]{0, start, 0});while(!queue.isEmpty()){//取出来int[] arr = queue.poll();int time = arr[0];int cur = arr[1];int power = arr[2];//继续if(time > res[cur][power]) continue;//结束if(cur == end) return time;//充一次电//新时间 = 已用时间 + 当前城市每单位充电需要时间， 新电量 = 剩余电量 + 1if(power < cnt){int t = time + charge[cur];if(t < res[cur][power+1]){res[cur][power+1] = t;queue.offer(new int[]{t, cur, power+1});}}//去往下一个城市//新时间 = 已用时间 + 去往该需要消耗的时间， 新电量 = 剩余电量 − 去往该城市需要消耗的电量for(int[] path : map[cur]){int next = path[0];int cost = path[1];int t = time + cost;int p = power - cost;if(p >= 0 && t < res[next][p]){res[next][p] = t;queue.offer(new int[]{t, next, p});}}}return -1;}
}

最后

我们都有光明的未来

祝大家考研上岸
祝大家工作顺利
祝大家得偿所愿
祝大家如愿以偿
点赞收藏关注哦