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和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键

如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

《如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)》:本文主要介绍如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)问题,具有很好的参考价值,希望对大家有所帮助,如有... 目录先在你打算存放的地方建四个文件夹更改这四个路径就可以修改默认虚拟内存分页js文件的位置接下来从高级-

一文详解如何查看本地MySQL的安装路径

《一文详解如何查看本地MySQL的安装路径》本地安装MySQL对于初学者或者开发人员来说是一项基础技能,但在安装过程中可能会遇到各种问题,:本文主要介绍如何查看本地MySQL安装路径的相关资料,需... 目录1. 如何查看本地mysql的安装路径1.1. 方法1:通过查询本地服务1.2. 方法2:通过MyS

Linux搭建单机MySQL8.0.26版本的操作方法

《Linux搭建单机MySQL8.0.26版本的操作方法》:本文主要介绍Linux搭建单机MySQL8.0.26版本的操作方法,本文通过图文并茂的形式给大家讲解的非常详细,感兴趣的朋友一起看看吧... 目录概述环境信息数据库服务安装步骤下载前置依赖服务下载方式一:进入官网下载,并上传到宿主机中,适合离线环境

Python如何调用指定路径的模块

《Python如何调用指定路径的模块》要在Python中调用指定路径的模块,可以使用sys.path.append,importlib.util.spec_from_file_location和exe... 目录一、sys.path.append() 方法1. 方法简介2. 使用示例3. 注意事项二、imp

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod