本文主要是介绍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力扣每日一题——设计可以求最短路径的图类的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!