网站优化 价格,广告设计软件免费下载,企业类型,中山网站建设品牌class065 A星、Floyd、Bellman-Ford与SPFA【算法】
2023-12-9 19:27:02
算法讲解065【必备】A星、Floyd、Bellman-Ford与SPFA code1 A*算法模版
// A*算法模版#xff08;对数器验证#xff09;
package class065;import java.util.PriorityQueue;// A*算法模版#xff…class065 A星、Floyd、Bellman-Ford与SPFA【算法】
2023-12-9 19:27:02
算法讲解065【必备】A星、Floyd、Bellman-Ford与SPFA code1 A*算法模版
// A*算法模版对数器验证
package class065;import java.util.PriorityQueue;// A*算法模版对数器验证
public class Code01_AStarAlgorithm {// 0:上1:右2:下3:左public static int[] move new int[] { -1, 0, 1, 0, -1 };// Dijkstra算法// grid[i][j] 0 代表障碍// grid[i][j] 1 代表道路// 只能走上、下、左、右不包括斜线方向// 返回从(startX, startY)到(targetX, targetY)的最短距离public static int minDistance1(int[][] grid, int startX, int startY, int targetX, int targetY) {if (grid[startX][startY] 0 || grid[targetX][targetY] 0) {return -1;}int n grid.length;int m grid[0].length;int[][] distance new int[n][m];for (int i 0; i n; i) {for (int j 0; j m; j) {distance[i][j] Integer.MAX_VALUE;}}distance[startX][startY] 1;boolean[][] visited new boolean[n][m];PriorityQueueint[] heap new PriorityQueue((a, b) - a[2] - b[2]);// 0 : 行// 1 : 列// 2 : 从源点出发到达当前点的距离heap.add(new int[] { startX, startY, 1 });while (!heap.isEmpty()) {int[] cur heap.poll();int x cur[0];int y cur[1];if (visited[x][y]) {continue;}visited[x][y] true;if (x targetX y targetY) {return distance[x][y];}for (int i 0, nx, ny; i 4; i) {nx x move[i];ny y move[i 1];if (nx 0 nx n ny 0 ny m grid[nx][ny] 1 !visited[nx][ny] distance[x][y] 1 distance[nx][ny]) {distance[nx][ny] distance[x][y] 1;heap.add(new int[] { nx, ny, distance[x][y] 1 });}}}return -1;}// A*算法// grid[i][j] 0 代表障碍// grid[i][j] 1 代表道路// 只能走上、下、左、右不包括斜线方向// 返回从(startX, startY)到(targetX, targetY)的最短距离public static int minDistance2(int[][] grid, int startX, int startY, int targetX, int targetY) {if (grid[startX][startY] 0 || grid[targetX][targetY] 0) {return -1;}int n grid.length;int m grid[0].length;int[][] distance new int[n][m];for (int i 0; i n; i) {for (int j 0; j m; j) {distance[i][j] Integer.MAX_VALUE;}}distance[startX][startY] 1;boolean[][] visited new boolean[n][m];// 0 : 行// 1 : 列// 2 : 从源点出发到达当前点的距离 当前点到终点的预估距离PriorityQueueint[] heap new PriorityQueue((a, b) - a[2] - b[2]);heap.add(new int[] { startX, startY, 1 f1(startX, startY, targetX, targetY) });while (!heap.isEmpty()) {int[] cur heap.poll();int x cur[0];int y cur[1];if (visited[x][y]) {continue;}visited[x][y] true;if (x targetX y targetY) {return distance[x][y];}for (int i 0, nx, ny; i 4; i) {nx x move[i];ny y move[i 1];if (nx 0 nx n ny 0 ny m grid[nx][ny] 1 !visited[nx][ny] distance[x][y] 1 distance[nx][ny]) {distance[nx][ny] distance[x][y] 1;heap.add(new int[] { nx, ny, distance[x][y] 1 f1(nx, ny, targetX, targetY) });}}}return -1;}// 曼哈顿距离public static int f1(int x, int y, int targetX, int targetY) {return (Math.abs(targetX - x) Math.abs(targetY - y));}// 对角线距离public static int f2(int x, int y, int targetX, int targetY) {return Math.max(Math.abs(targetX - x), Math.abs(targetY - y));}// 欧式距离public static double f3(int x, int y, int targetX, int targetY) {return Math.sqrt(Math.pow(targetX - x, 2) Math.pow(targetY - y, 2));}// 为了测试public static int[][] randomGrid(int n) {int[][] grid new int[n][n];for (int i 0; i n; i) {for (int j 0; j n; j) {if (Math.random() 0.3) {// 每个格子有30%概率是0grid[i][j] 0;} else {// 每个格子有70%概率是1grid[i][j] 1;}}}return grid;}// 为了测试public static void main(String[] args) {int len 100;int testTime 10000;System.out.println(功能测试开始);for (int i 0; i testTime; i) {int n (int) (Math.random() * len) 2;int[][] grid randomGrid(n);int startX (int) (Math.random() * n);int startY (int) (Math.random() * n);int targetX (int) (Math.random() * n);int targetY (int) (Math.random() * n);int ans1 minDistance1(grid, startX, startY, targetX, targetY);int ans2 minDistance2(grid, startX, startY, targetX, targetY);if (ans1 ! ans2) {System.out.println(出错了!);}}System.out.println(功能测试结束);System.out.println(性能测试开始);int[][] grid randomGrid(4000);int startX 0;int startY 0;int targetX 3900;int targetY 3900;long start, end;start System.currentTimeMillis();int ans1 minDistance1(grid, startX, startY, targetX, targetY);end System.currentTimeMillis();System.out.println(运行dijskra算法结果: ans1 , 运行时间(毫秒) : (end - start));start System.currentTimeMillis();int ans2 minDistance2(grid, startX, startY, targetX, targetY);end System.currentTimeMillis();System.out.println(运行A*算法结果: ans2 , 运行时间(毫秒) : (end - start));System.out.println(性能测试结束);}}
code2 P2910 [USACO08OPEN] Clear And Present Danger S
// Floyd算法模版洛谷 // 测试链接 : https://www.luogu.com.cn/problem/P2910 // 请同学们务必参考如下代码中关于输入、输出的处理 // 这是输入输出处理效率很高的写法 // 提交以下所有代码把主类名改成Main可以直接通过
package class065;// Floyd算法模版洛谷
// 测试链接 : https://www.luogu.com.cn/problem/P2910
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码把主类名改成Main可以直接通过import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Code02_Floyd {public static int MAXN 101;public static int MAXM 10001;public static int[] path new int[MAXM];public static int[][] distance new int[MAXN][MAXN];public static int n, m, ans;// 初始时设置任意两点之间的最短距离为无穷大表示任何路不存在public static void build() {for (int i 0; i n; i) {for (int j 0; j n; j) {distance[i][j] Integer.MAX_VALUE;}}}public static void main(String[] args) throws IOException {BufferedReader br new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in new StreamTokenizer(br);PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));while (in.nextToken() ! StreamTokenizer.TT_EOF) {n (int) in.nval;in.nextToken();m (int) in.nval;for (int i 0; i m; i) {in.nextToken();path[i] (int) in.nval - 1;}// 这道题给的图是邻接矩阵的形式// 任意两点之间的边权都会给定// 所以显得distance初始化不太必要// 但是一般情况下distance初始化一定要做build();for (int i 0; i n; i) {for (int j 0; j n; j) {in.nextToken();distance[i][j] (int) in.nval;}}floyd();ans 0;for (int i 1; i m; i) {ans distance[path[i - 1]][path[i]];}out.println(ans);}out.flush();out.close();br.close();}public static void floyd() {// O(N^3)的过程// 枚举每个跳板// 注意跳板要最先枚举跳板要最先枚举跳板要最先枚举for (int bridge 0; bridge n; bridge) { // 跳板for (int i 0; i n; i) {for (int j 0; j n; j) {// i - .....bridge .... - j// distance[i][j]能不能缩短// distance[i][j] min ( distance[i][j] , distance[i][bridge] distance[bridge][j])if (distance[i][bridge] ! Integer.MAX_VALUE distance[bridge][j] ! Integer.MAX_VALUE distance[i][j] distance[i][bridge] distance[bridge][j]) {distance[i][j] distance[i][bridge] distance[bridge][j];}}}}}}
code3 787. K 站中转内最便宜的航班
// Bellman-Ford算法应用不是模版 // k站中转内最便宜的航班 // 有 n 个城市通过一些航班连接。给你一个数组 flights // 其中 flights[i] [fromi, toi, pricei] // 表示该航班都从城市 fromi 开始以价格 pricei 抵达 toi。 // 现在给定所有的城市和航班以及出发城市 src 和目的地 dst你的任务是找到出一条最多经过 k 站中转的路线 // 使得从 src 到 dst 的 价格最便宜 并返回该价格。 如果不存在这样的路线则输出 -1。 // 测试链接 : https://leetcode.cn/problems/cheapest-flights-within-k-stops/
package class065;import java.util.Arrays;// Bellman-Ford算法应用不是模版
// k站中转内最便宜的航班
// 有 n 个城市通过一些航班连接。给你一个数组 flights
// 其中 flights[i] [fromi, toi, pricei]
// 表示该航班都从城市 fromi 开始以价格 pricei 抵达 toi。
// 现在给定所有的城市和航班以及出发城市 src 和目的地 dst你的任务是找到出一条最多经过 k 站中转的路线
// 使得从 src 到 dst 的 价格最便宜 并返回该价格。 如果不存在这样的路线则输出 -1。
// 测试链接 : https://leetcode.cn/problems/cheapest-flights-within-k-stops/
public class Code03_BellmanFord {// Bellman-Ford算法// 针对此题改写了松弛逻辑课上讲了细节public static int findCheapestPrice(int n, int[][] flights, int start, int target, int k) {int[] cur new int[n];Arrays.fill(cur, Integer.MAX_VALUE);cur[start] 0;for (int i 0; i k; i) {int[] next Arrays.copyOf(cur, n);for (int[] edge : flights) {// a - b , wif (cur[edge[0]] ! Integer.MAX_VALUE) {next[edge[1]] Math.min(next[edge[1]], cur[edge[0]] edge[2]);}}cur next;}return cur[target] Integer.MAX_VALUE ? -1 : cur[target];}}
P3385 【模板】负环
// Bellman-Ford SPFA优化模版洛谷 // 给定一个 n个点的有向图请求出图中是否存在从顶点 1 出发能到达的负环 // 负环的定义是一条边权之和为负数的回路。 // 测试链接 : https://www.luogu.com.cn/problem/P3385 // 请同学们务必参考如下代码中关于输入、输出的处理 // 这是输入输出处理效率很高的写法 // 提交以下所有代码把主类名改成Main可以直接通过
package class065;// Bellman-Ford SPFA优化模版洛谷
// 给定一个 n个点的有向图请求出图中是否存在从顶点 1 出发能到达的负环
// 负环的定义是一条边权之和为负数的回路。
// 测试链接 : https://www.luogu.com.cn/problem/P3385
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码把主类名改成Main可以直接通过import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Code04_SPFA {public static int MAXN 2001;public static int MAXM 6001;// 链式前向星建图需要public static int[] head new int[MAXN];public static int[] next new int[MAXM];public static int[] to new int[MAXM];public static int[] weight new int[MAXM];public static int cnt;// SPFA需要public static int MAXQ 4000001;// 源点出发到每个节点的距离表public static int[] distance new int[MAXN];// 节点被松弛的次数public static int[] updateCnt new int[MAXN];// 哪些节点被松弛了放入队列public static int[] queue new int[MAXQ];public static int l, r;// 节点是否已经在队列中public static boolean[] enter new boolean[MAXN];public static void build(int n) {cnt 1;l r 0;Arrays.fill(head, 1, n 1, 0);Arrays.fill(enter, 1, n 1, false);Arrays.fill(distance, 1, n 1, Integer.MAX_VALUE);Arrays.fill(updateCnt, 1, n 1, 0);}public static void addEdge(int u, int v, int w) {next[cnt] head[u];to[cnt] v;weight[cnt] w;head[u] cnt;}public static void main(String[] args) throws IOException {BufferedReader br new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in new StreamTokenizer(br);PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int cases (int) in.nval;for (int i 0, n, m; i cases; i) {in.nextToken(); n (int) in.nval;in.nextToken(); m (int) in.nval;build(n);for (int j 0, u, v, w; j m; j) {in.nextToken(); u (int) in.nval;in.nextToken(); v (int) in.nval;in.nextToken(); w (int) in.nval;if (w 0) {addEdge(u, v, w);addEdge(v, u, w);} else {addEdge(u, v, w);}}out.println(spfa(n) ? YES : NO);}out.flush();out.close();br.close();}// Bellman-Ford SPFA优化的模版public static boolean spfa(int n) {distance[1] 0;updateCnt[1];queue[r] 1;enter[1] true;while (l r) {int u queue[l];enter[u] false;for (int ei head[u], v, w; ei 0; ei next[ei]) {v to[ei];w weight[ei];if (distance[u] w distance[v]) {distance[v] distance[u] w;if (!enter[v]) {if (updateCnt[v] n) {return true;}queue[r] v;enter[v] true;}}}}return false;}}
2023-12-9 21:16:55
