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

本文主要是介绍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$ )

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;}
}