class065 A星、Floyd、Bellman-Ford与SPFA【算法】-摩杜云开发者社区

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

2023-12-9 19:27:02

算法讲解065【必备】A星、Floyd、Bellman-Ford与SPFA

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

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

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

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

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

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

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

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