首页 > 编程语言 >class065 A星、Floyd、Bellman-Ford与SPFA【算法】

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

时间：2023-12-21 14:02:34浏览次数：34  
标签：distance class065 int Bellman grid SPFA static new public


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

2023-12-9 19:27:02

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

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

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


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

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


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


class065 A星、Floyd、Bellman-Ford与SPFA【算法】_System_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


标签：distance,class065,int,Bellman,grid,SPFA,static,new,public
From： https://blog.51cto.com/u_15719556/8923449

相关文章

  • 【图论】差分约束与SPFA 11.25学习小结
    开篇碎碎念每次都是以开篇碎碎念开头，虽然不知道为什么，但似乎成为了惯例。本来是直接看的差分约束，一上来发现一堆不等式，以为是数学的一个tag乱入图论(x，结果发现还真的是建图来做的，然后学了一下之后...负边权？！跑不了dijkstra啊！！于是学了一下SPFA（虽然...SPFA已死）然后顺道写了一下关于......
  • AcWing 3305. 作物杂交 (spfa建边变形版本
    package蓝桥杯;importjava.util.Arrays;importjava.util.LinkedList;importjava.util.Queue;importjava.util.Scanner;publicclasslanqiao1443{staticfinalintN=2010,M=2*100010;staticint[]h,e,ne,w,target;staticint[]dist;......
  • bellman_ford算法
    Bellman–Ford算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。有边数限制的最短路普通做法intne[N],h[N],idx,e[N],wt[N];//wt[]表示边权voidadd(intu,intv,intw)//链式前向星存图{idx++;......
  • spfa算法（求最短路和判断是否存在负环）floyd求最短路（11/1）
    #include<iostream>#include<cstring>#include<algorithm>#include<queue>usingnamespacestd;constintN=100010;intn,m;inth[N];intne[N];inte[N],w[N],idx=0;intdist[N];boolst[N];voidadd(inta,intb,intc){ne[idx]=......
  • 我的无优化 SPFA 果然有问题
    SPFA是一个非常好用的最短路径算法，可以跑负边权、判负环。但总有一些良心出题人要卡掉它。我是SPFA小姐的狗！可爱的SPFA娘“单源最短路啊？人家最擅长啦！”10minslater“唔……应该是这样……然后这样……诶诶怎么还没有处理完啦！这个数据好讨厌的QAQ”“话说这个数据没......
  • spfa---模板
    spfa模板#include<stdio.h>#include<string.h>#include<stdlib.h>#include<queue>usingnamespacestd;#defineV1010//点的个数#defineE4020//变的个数*2(双向边)#defineINF0x3f3f3f3fstructnode{ inta,b,len;}p[E];intnex[E];intfirs......
  • spfa在使用中问题的简单分析
    作者水平一般，有问题请指出，我将及时修改。〇、问题引入spfa本质上是队列优化贝尔曼福特。我们可以使用队列，在每一轮的点更新中仅更新上一轮更新中的被更新点的相邻的点（好绕……）。这种情况下的算法复杂度与Dijkstra不相上下。但是有一个问题，这么好的算法为什么没有被大量......
  • AcWing 852. spfa判断负环
    题目给定一个$n$个点$m$条边的有向图，图中可能存在重边和自环，边权可能为负数。请你判断图中是否存在负权回路。输入格式第一行包含整数$n$和$m$。接下来$m$行每行包含三个整数$x,y,z$，表示存在一条从点$x$到点$y$的有向边，边长为$z$。输出格式如果图中存在负......
  • AcWing 851. spfa求最短路
    题目给定一个$n$个点$m$条边的有向图，图中可能存在重边和自环，边权可能为负数。请你求出$1$号点到$n$号点的最短距离，如果无法从$1$号点走到$n$号点，则输出impossible。数据保证不存在负权回路。输入格式第一行包含整数$n$和$m$。接下来$m$行每行包含三个整......
  • 【RL】CH2-Bellman equation
    thediscountedreturn\[\begin{aligned}G_t&=R_{t+1}+\gammaR_{t+2}+\gamma^2R_{t+3}+\ldots\\&=R_{t+1}+\gamma\left(R_{t+2}+\gammaR_{t+3}+\ldots\right)\\&=R_{t+1}+\gammaG_{t+1}\end{aligned}\]state-valuefunction/the......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99