网站ui设计报价单,5g全连接工厂建设指南,优质的外国网站,凡客诚品官网网址单源最短路径【学习算法】 前言版权推荐单源最短路径Java算法实现代码结果 带限制的单源最短路径1928. 规定时间内到达终点的最小花费LCP 35. 电动车游城市 最后 前言
2023-8-14 18:21:41
以下内容源自《【学习算法】》 仅供学习交流使用
版权
禁止其他平台发布时删除以下此… 单源最短路径【学习算法】 前言版权推荐单源最短路径Java算法实现代码结果 带限制的单源最短路径1928. 规定时间内到达终点的最小花费LCP 35. 电动车游城市 最后 前言
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((VE)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) {//邻接表Listint[][] 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;//优先队列PriorityQueueint[] 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) {//邻接表Listint[][] 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;//优先队列PriorityQueueint[] 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 (vertexend){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;//构造图邻接表ListListint[] 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});}//优先队列PriorityQueueint[] queue new PriorityQueue(Comparator.comparingInt(a - a[1]));//时间 花费 当前结点queue.add(new int[]{0, passingFees[0], 0});//到达node的最少时间MapInteger, 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;//构造了图Listint[][] 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][cnt1];for(int[] i : res) Arrays.fill(i, Integer.MAX_VALUE/2);res[start][0] 0;//用队列来记录每个路径的信息 {time,cur,power}//time 已用时间 cur 所在城市 power 剩余电量//(使用优先队列来保证每次优先执行已用时间最少的路径)Queueint[] queue new PriorityQueueint[]((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][power1]){res[cur][power1] t;queue.offer(new int[]{t, cur, power1});}}//去往下一个城市//新时间 已用时间 去往该需要消耗的时间 新电量 剩余电量 − 去往该城市需要消耗的电量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;}
}
最后
我们都有光明的未来
祝大家考研上岸 祝大家工作顺利 祝大家得偿所愿 祝大家如愿以偿 点赞收藏关注哦
