class065 A星、Floyd、Bellman-Ford与SPFA【算法】

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];
		PriorityQueue<int[]> 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 : 从源点出发到达当前点的距离 + 当前点到终点的预估距离
		PriorityQueue<int[]> 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%概率是0
					grid[i][j] = 0;
				} else {
					// 每个格子有70%概率是1
					grid[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 , w
				if (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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/233928.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Mysql8.0实现主从复制

1、什么是主从复制 数据库的主从复制&#xff08;master-slave replication&#xff09;是一种数据复制技术&#xff0c;其中一台数据库服务器&#xff08;主服务器&#xff09;上的数据变更会复制到另一台或多台数据库服务器&#xff08;从服务器&#xff09;上。这种复制可以…

【Copilot】Edge浏览器的copilot消失了怎么办

这种原因&#xff0c;可能是因为你的ip地址的不在这个服务的允许范围内。你需要重新使用之前出现copilot的ip地址&#xff0c;然后退出edge的账号&#xff0c;重新登录一遍&#xff0c;最后重启edge&#xff0c;就能够使得copilot侧边栏重新出现了。

C语言算法与数据结构,旅游景区地图求最短路径

背景&#xff1a; 本次作业要求完成一个编程项目。请虚构一张旅游景区地图&#xff0c;景区地图包括景点&#xff08;结点&#xff09;和道路&#xff08;边&#xff09;&#xff1a;地图上用字母标注出一些点&#xff0c;表示景点&#xff08;比如&#xff0c;以点 A、B、C、…

线程及实现方式

一、线程 线程是一个基本的CPU执行单元&#xff0c;也是程序执行流的最小单位。引入线程之后&#xff0c;不仅是进程之间可以并发&#xff0c;进程内的各线程之间也可以并发&#xff0c;从而进一步提升了系统的并发度&#xff0c;使得一个进程内也可以并发处理各种任务&#x…

漏洞复现-大华dss struts2-045表达式注入漏洞(附漏洞检测脚本)

免责声明 文章中涉及的漏洞均已修复&#xff0c;敏感信息均已做打码处理&#xff0c;文章仅做经验分享用途&#xff0c;切勿当真&#xff0c;未授权的攻击属于非法行为&#xff01;文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直接或者间接的…

EdgeYOLO: anchor-free,边缘部署友好

简体中文 1 Intro 2 Updates 3 Coming Soon 4 Models 5 Quick Start \quad 5.1 setup

Leetcode刷题笔记题解(C++):92. 反转链表 II

思路&#xff1a;获取要反转的区间&#xff0c;拆开之后进行反转再拼接 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* …

我有才专属定制适合个人的知识付费平台,打造个性化品牌与自主管理体验

在当今数字化时代&#xff0c;知识付费平台已经成为人们获取专业知识、提升自身素质的重要渠道。然而&#xff0c;公共知识付费平台虽然内容丰富&#xff0c;但难以满足个人或企业个性化的需求和品牌打造。因此&#xff0c;我们提出了专属定制适合个人的知识付费平台的概念&…

题目:跳石头(蓝桥OJ 364)

题目描述&#xff1a; 解题思路&#xff1a; 注意点&#xff1a;二分需要一些冗余&#xff0c;即遍历的r大小可能比需要建立的数组大。 题解&#xff1a; #include<bits/stdc.h> using namespace std; const int N 5e4 9; using ll long long; int L, n, m; int a[N…

55.手写实现grpc连接池以及gin和grpc交互

文章目录 一、简介前置说明 二、敏感词过滤服务1、定义sensitive.proto文件2、protoc生成pb.go文件3、sensitive服务端实现 三、关键词匹配服务1、编写keywords.proto文件2、生成pb.go文件3、keywords服务端实现 四、gin web 路由服务1、新建grpcpool服务作为gin web服务2、根据…

202301209将RK3399的挖掘机开发板在Android10下设置系统默认为24小时制

202301209将RK3399的挖掘机开发板在Android10下设置系统默认为24小时制 2023/12/9 22:07 应该也可以适用于RK3399的Android12系统 --- a/frameworks/base/packages/SettingsProvider/res/values/defaults.xml b/frameworks/base/packages/SettingsProvider/res/values/default…

AtCoder Beginner Contest 328

A - Not Too Hard (atcoder.jp) AC代码: #include<bits/stdc.h> #define endl \n //#define int long long using namespace std; const int N10; int s[N]; int n,x; void solve() {cin>>n>>x;for(int i1;i<n;i) cin>>s[i];int ans0;for(int i1;…

【现代信息检索】国科大何苯老师现代信息检索课程作业 —— 第一次作业

1 考虑如下几篇文档&#xff1a; 文档1&#xff1a;new home sales top forecasts 文档2&#xff1a;home prices rise in june 文档3&#xff1a;increase in home sales in june 文档4&#xff1a;july new home sales rise a. 画出文档集对应的词项-文档矩阵。 文档 1文…

java--DateTimeFormatter、Period、Duration

1.DateTimeFormatter 2.LocalDateTime提供的格式化、解析时间的方法 3.Period(一段时期) 可以用于计算两个LocalDate对象相差的年数、月数、天数。 4.Duration(持续时间) 可以用于计算两个时间对象相差的天数、小时数、分数、秒数、纳秒数&#xff1b;支持LocalTime、LocalDa…

linux通过命令切换用户

在Linux中&#xff0c;你可以使用su&#xff08;substitute user或switch user&#xff09;命令来切换用户。这个命令允许你临时或永久地以另一个用户的身份运行命令。以下是基本的用法&#xff1a; 基本切换到另一个用户&#xff08;需要密码&#xff09;&#xff1a;su [用户…

【数据结构】哈希表算法总结

知识概览&#xff08;哈希表&#xff09; 哈希表可以将一些值域较大的数映射到较小的空间内&#xff0c;通常用x mod 质数的方式进行映射。为什么用质数呢&#xff1f;这样的质数还要离2的整数幂尽量远。这可以从数学上证明&#xff0c;这样冲突最小。取余还是会出现冲突情况。…

智慧工地安全管理方案,智慧工地云平台源码,java项目源码

智慧工地安全管理方案&#xff0c;智慧工地云平台源码 智慧工地是一种以信息技术为手段&#xff0c;全面提升建筑施工过程的管理水平、提高工程质量和安全、降低工程成本和风险、提高施工效率和管理水平的智能化技术和系统。通过物联网、互联网、大数据、云计算等技术的应用&a…

跟着chatgpt一起学|clickhouse入门(3)MergeTree

跟着chatgpt一起学|2.clickhouse入门&#xff08;1&#xff09;-CSDN博客 跟着chatgpt一起学|2.Clickhouse入门&#xff08;2&#xff09;-CSDN博客 chatgpt规划的学习路径如下&#xff1a; 3.MergeTree的分类和适用场景 MergeTree 引擎是 ClickHouse 中最为强大和多用途的引…

linux Ubuntu下,第一个C++程序访问数据库,遇到的问题,及解决办法

在ubuntu下安装了mysql&#xff0c;mysql以后&#xff0c;编写了第一个访问数据库的程序&#xff1a; #include <iostream> #include <string> #include <cstdlib> //for system #include <mysql.h>using namespace std;int main() {mysqlpp::Connect…

文心一言API(高级版)使用

文心一言API高级版使用 一、百度文心一言API(高级版)二、使用步骤1、接口2、请求参数3、请求参数示例4、接口 返回示例 三、 如何获取appKey和uid1、申请appKey:2、获取appKey和uid 四、重要说明 一、百度文心一言API(高级版) 基于百度文心一言语言大模型的智能文本对话AI机器…
最新文章