营销网站html,网页游戏平台代理,网站首页排名seo搜索优化,wordpress教程哪本好2024.3.26 题目来源我的题解方法一 Dijkstra算法求最短路径方法二 Floyd算法求最短路径 题目来源
力扣每日一题#xff1b;题序#xff1a;2642
我的题解
方法一 Dijkstra算法求最短路径 图使用邻接表存储#xff0c;添加边只需要更新邻接表就行。 求两个节点的路径最小代… 2024.3.26 题目来源我的题解方法一 Dijkstra算法求最短路径方法二 Floyd算法求最短路径 题目来源
力扣每日一题题序2642
我的题解
方法一 Dijkstra算法求最短路径 图使用邻接表存储添加边只需要更新邻接表就行。 求两个节点的路径最小代价使用dijkstra算法来实现 时间复杂度 Graph 类初始化时时间复杂度为 O(m)其中 mmm 表示给定的 edges 数组的长度。调用 addEdge时此时直接在邻接边中添加一条边即可时间复杂度为 O(1) 。调用 shortestPath 时需要的时间复杂度为 O((mk)log(mk))其中 m 表示给定的 edges 数组的长度k 表示调用 addEdge的次数。使用优先队列的 「Dijkstra 算法」的时间度与图中边的数量关系有关需要的时间即为O((mk)log(mk))。 空间复杂度O(mnk)。n表示给定的节点数。 class Graph {ListInteger[] g;int N101;public Graph(int n, int[][] edges) {gcreateGraph(n,edges);}private ListInteger[] createGraph(int n,int[][] edges){ListInteger[] gnew ArrayList[N];for(int i0;iN;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){PriorityQueueint[] pq new PriorityQueueint[]((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 i0;ig[cur].size();i2) {int next g[cur].get(i), ncost g[cur].get(i1);// 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(n3m)其中 m 表示给定的 edges 数组的长度n 表示给定的节点数目 n。初始边时需要的时间为 O(m)使用「Floyd 算法」求任意两条边的最短路径需要的时间复杂度为 O(n3)总的时间为 O(n3m)。调用 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;}
}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
