2024.3.26力扣每日一题——设计可以求最短路径的图类

2024-04-08 18:12

本文主要是介绍2024.3.26力扣每日一题——设计可以求最短路径的图类,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2024.3.26

      • 题目来源
      • 我的题解
        • 方法一 Dijkstra算法求最短路径
        • 方法二 Floyd算法求最短路径

题目来源

力扣每日一题;题序:2642

我的题解

方法一 Dijkstra算法求最短路径

图使用邻接表存储,添加边只需要更新邻接表就行。
求两个节点的路径最小代价使用dijkstra算法来实现

时间复杂度

  • Graph 类初始化时,时间复杂度为 O(m),其中 mmm 表示给定的 edges 数组的长度。
  • 调用 addEdge时,此时直接在邻接边中添加一条边即可,时间复杂度为 O(1) 。
  • 调用 shortestPath 时,需要的时间复杂度为 O((m+k)log⁡(m+k)),其中 m 表示给定的 edges 数组的长度,k 表示调用 addEdge的次数。使用优先队列的 「Dijkstra 算法」的时间度与图中边的数量关系有关,需要的时间即为O((m+k)log⁡(m+k))。

空间复杂度:O(m+n+k)。n表示给定的节点数。

class Graph {List<Integer>[] g;int N=101;public Graph(int n, int[][] edges) {g=createGraph(n,edges);}private List<Integer>[] createGraph(int n,int[][] edges){List<Integer>[] g=new ArrayList[N];for(int i=0;i<N;i++)g[i]=new ArrayList<>();for(int[] t:edges){int from = t[0];int to = t[1];int w = t[2];g[from].add(to);g[from].add(w);}return g;}public void addEdge(int[] edge) {int from = edge[0];int to = edge[1];int w = edge[2];g[from].add(to);g[from].add(w);}public int shortestPath(int node1, int node2) {return dijkstra(node1,node2); }private int dijkstra(int root,int target){PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);int[] dist = new int[g.length];Arrays.fill(dist, Integer.MAX_VALUE);dist[root] = 0;pq.offer(new int[]{0, root});while (!pq.isEmpty()) {int[] arr = pq.poll();int cost = arr[0], cur = arr[1];if (cur == target) {return cost;}for (int i=0;i<g[cur].size();i+=2) {int next = g[cur].get(i), ncost = g[cur].get(i+1);// System.out.println(next+" "+ncost);if (dist[next] > cost + ncost) {dist[next] = cost + ncost;pq.offer(new int[]{cost + ncost, next});}}}return -1;}
}
方法二 Floyd算法求最短路径

不需要单独存储图,只需要使用一个矩阵存储各个节点之间的最短距离,然后利用Floyd算法求最短路径。优点在于:不用每次addEdge之后需要重新计算每个点之间的最短距离,而是采用更新的方式进行更新。

时间复杂度

  • Graph 类初始化时,时间复杂度为 O(n3+m),其中 m 表示给定的 edges 数组的长度,n 表示给定的节点数目 n。初始边时需要的时间为 O(m),使用「Floyd 算法」求任意两条边的最短路径需要的时间复杂度为 O(n3),总的时间为 O(n3+m)。
  • 调用 addEdge 时,Floyd 本质为动态规划,增加一条新的边时需要动态更新,此时需要的时间复杂度为 O(n2)。
  • 调用 shortestPath 时,需要的时间为 O(1)。

空间复杂度:O( n 2 n^2 n2)

class Graph {private int[][] dist;public Graph(int n, int[][] edges) {dist = new int[n][n];for (int i = 0; i < n; i++) {Arrays.fill(dist[i], Integer.MAX_VALUE);dist[i][i] = 0;}for (int[] edge : edges) {dist[edge[0]][edge[1]] = edge[2];}for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);}}}}}public void addEdge(int[] edge) {int x = edge[0], y = edge[1], cost = edge[2];if (cost >= dist[x][y]) {return;}int n = dist.length;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (dist[i][x] != Integer.MAX_VALUE && dist[y][j] != Integer.MAX_VALUE) {dist[i][j] = Math.min(dist[i][j], dist[i][x] + cost + dist[y][j]);}}}}public int shortestPath(int node1, int node2) {int res = dist[node1][node2];return res == Integer.MAX_VALUE ? -1 : res;}
}

有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

这篇关于2024.3.26力扣每日一题——设计可以求最短路径的图类的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/886221

相关文章

Python中的可视化设计与UI界面实现

《Python中的可视化设计与UI界面实现》本文介绍了如何使用Python创建用户界面(UI),包括使用Tkinter、PyQt、Kivy等库进行基本窗口、动态图表和动画效果的实现,通过示例代码,展示... 目录从像素到界面:python带你玩转UI设计示例:使用Tkinter创建一个简单的窗口绘图魔法:用

python获取当前文件和目录路径的方法详解

《python获取当前文件和目录路径的方法详解》:本文主要介绍Python中获取当前文件路径和目录的方法,包括使用__file__关键字、os.path.abspath、os.path.realp... 目录1、获取当前文件路径2、获取当前文件所在目录3、os.path.abspath和os.path.re

Linux下MySQL8.0.26安装教程

《Linux下MySQL8.0.26安装教程》文章详细介绍了如何在Linux系统上安装和配置MySQL,包括下载、解压、安装依赖、启动服务、获取默认密码、设置密码、支持远程登录以及创建表,感兴趣的朋友... 目录1.找到官网下载位置1.访问mysql存档2.下载社区版3.百度网盘中2.linux安装配置1.

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

怎么让1台电脑共享给7人同时流畅设计

在当今的创意设计与数字内容生产领域,图形工作站以其强大的计算能力、专业的图形处理能力和稳定的系统性能,成为了众多设计师、动画师、视频编辑师等创意工作者的必备工具。 设计团队面临资源有限,比如只有一台高性能电脑时,如何高效地让七人同时流畅地进行设计工作,便成为了一个亟待解决的问题。 一、硬件升级与配置 1.高性能处理器(CPU):选择多核、高线程的处理器,例如Intel的至强系列或AMD的Ry

基于51单片机的自动转向修复系统的设计与实现

文章目录 前言资料获取设计介绍功能介绍设计清单具体实现截图参考文献设计获取 前言 💗博主介绍:✌全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师,一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设计 主要对象是咱们电子相关专业的大学生,希望您们都共创辉煌!✌💗 👇🏻 精彩专栏 推荐订阅👇🏻 单片机

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

SprinBoot+Vue网络商城海鲜市场的设计与实现

目录 1 项目介绍2 项目截图3 核心代码3.1 Controller3.2 Service3.3 Dao3.4 application.yml3.5 SpringbootApplication3.5 Vue 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍:CSDN认证博客专家,CSDN平台Java领域优质创作者,全网30w+