047.A星、Floyd、Bellman-Ford 与 SPFA

前置知识：建图、宽度优先遍历、Dijkstra 算法

备注：

【必备】标签下的课程，都是最基础、最高频的内容

有关图的更多内容，会在后续【扩展】、【挺难】标签下的课程中继续讲述

A* 算法 §

指定源点，指定目标点，求源点到达目标点的最短距离（如：游戏 NPC 寻路算法）

与 Dijkstra 算法 解决的问题差不多，只是 Dijkstra 是求所有点距原点的距离，A* 是只有一个目标点

那么 Dijkstra 也可以求（将其他无用点的结果舍弃即可），A* 也可以求？为什么非要用 A*，因为更快

与 Dijkstra 算法的思路也基本相同，只是增加了当前点到终点的预估函数，在堆中根据从源点出发到达当前点的距离+当前点到终点的预估距离来进行排序，剩下的所有细节和 Dijkstra 算法完全一致

预估函数要求：当前点到终点的预估距离 <= 当前点到终点的真实最短距离（否则可能导致答案错误）

可以理解预估函数是一种吸引力：

• 合适的吸引力可以提升算法的速度，吸引力过强会出现错误
• 保证预估距离 <= 真实最短距离的情况下，尽量接近真实最短距离，可以做到功能正确且最快

预估终点距离经常选择：

• 曼哈顿距离：$|x_0-x_1|+|y_0-y_1|$，只能走直线的情况
• 欧式距离：$\sqrt{(x_0-x_1{)}^2+(y_0-y_1{)}^2}$，即：勾股定理
• 对角线距离：$max(|x_0-x_1|,|y_0-y_1|)$，可以走对角线的情况

题目1.A* 算法模板 §

对数器验证，对比 Dijkstra 算法和 A* 算法的速度差异，以及不同预估函数的速度和正确性差异

题目描述 §

有一个二维网格 grid，它的每一个位置可能是 0（代表障碍）或 1（代表道路），求从 start 最少需要几步走到 end，只能向上下左右走

答案 §

package main
 
import (
	"container/heap"
	"fmt"
	"math"
	"math/rand"
	"time"
)
 
const (
	MAX_INT = math.MaxInt
)
 
var (
	move = [5]int{-1, 0, 1, 0, -1}
)
 
// 普通 bfs
func minDistance0(grid [][]int, startX, startY, endX, endY int) int {
	if grid[startX][startY] == 0 || grid[endX][endY] == 0 {
		return -1
	}
	n := len(grid)
	visited := make([][]bool, n)
	for i := range visited {
		visited[i] = make([]bool, n)
	}
	queue := [][2]int{{startX, startY}}
	level := 1
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			x := queue[i][0]
			y := queue[i][1]
			if visited[x][y] {
				continue
			}
			if x == endX && y == endY {
				return level
			}
			visited[x][y] = true
			for j := 0; j < 4; j++ {
				nx := x + move[j]
				ny := y + move[j+1]
				if nx < 0 || nx == n || ny < 0 || ny == n || visited[nx][ny] || grid[nx][ny] == 0 {
					continue
				}
				queue = append(queue, [2]int{nx, ny})
			}
		}
		level++
		queue = queue[size:]
	}
	return -1
}
 
// Dijkstra 算法
func minDistance1(grid [][]int, startX, startY, endX, endY int) int {
	if grid[startX][startY] == 0 || grid[endX][endY] == 0 {
		return -1
	}
	n := len(grid)
	distance := make([][]int, n)
	visited := make([][]bool, n)
	for i := range distance {
		distance[i] = make([]int, n)
		visited[i] = make([]bool, n)
		for j := 0; j < n; j++ {
			distance[i][j] = MAX_INT
		}
	}
	distance[startX][startY] = 1
	minHeap := MinHeap{}
	heap.Push(&minHeap, [3]int{startX, startY, 1})
	for len(minHeap) > 0 {
		record := heap.Pop(&minHeap).([3]int)
		x := record[0]
		y := record[1]
		if visited[x][y] {
			continue
		}
		if x == endX && y == endY {
			return distance[x][y]
		}
		visited[x][y] = true
		for i := 0; i < 4; i++ {
			nx := x + move[i]
			ny := y + move[i+1]
			if nx < 0 || nx == n || ny < 0 || ny == n || visited[nx][ny] || grid[nx][ny] == 0 {
				continue
			}
			if distance[nx][ny] > distance[x][y]+1 {
				distance[nx][ny] = distance[x][y] + 1
				heap.Push(&minHeap, [3]int{nx, ny, distance[nx][ny]})
			}
		}
	}
	return -1
}
 
// A* 算法
func minDistance2(grid [][]int, startX, startY, endX, endY int, f func(startX, startY, endX, endY int) int) int {
	if grid[startX][startY] == 0 || grid[endX][endY] == 0 {
		return -1
	}
	n := len(grid)
	distance := make([][]int, n)
	visited := make([][]bool, n)
	for i := range distance {
		distance[i] = make([]int, n)
		visited[i] = make([]bool, n)
		for j := 0; j < n; j++ {
			distance[i][j] = MAX_INT
		}
	}
	distance[startX][startY] = 1 // distance 还是记录的答案
	minHeap := MinHeap{}
	heap.Push(&minHeap, [3]int{startX, startY, 1 + f(startX, startY, endX, endY)}) // 堆中记录从源点出发到达当前点的距离 + 当前点到终点的预估距离
	for len(minHeap) > 0 {
		record := heap.Pop(&minHeap).([3]int)
		x := record[0]
		y := record[1]
		if visited[x][y] {
			continue
		}
		if x == endX && y == endY {
			return distance[x][y]
		}
		visited[x][y] = true
		for i := 0; i < 4; i++ {
			nx := x + move[i]
			ny := y + move[i+1]
			if nx < 0 || nx == n || ny < 0 || ny == n || visited[nx][ny] || grid[nx][ny] == 0 {
				continue
			}
			if distance[nx][ny] > distance[x][y]+1 {
				distance[nx][ny] = distance[x][y] + 1
				heap.Push(&minHeap, [3]int{nx, ny, distance[nx][ny] + f(nx, ny, endX, endY)})
			}
		}
	}
	return -1
}
 
// 曼哈顿距离
func f1(startX, startY, endX, endY int) int {
	return abs(startX-endX) + abs(startY-endY)
}
 
// 对角线距离
func f2(startX, startY, endX, endY int) int {
	return max(abs(startX-endX), abs(startY-endY))
}
 
// 欧式距离
func f3(startX, startY, endX, endY int) float64 {
	return math.Sqrt(math.Pow(float64(startX-endX), 2) + math.Pow(float64(startY-endY), 2))
}
 
// [x, y, 距离]
// Dijkstra: 距离是当前点到原点的距离
// A*: 从源点出发到达当前点的距离 + 当前点到终点的预估距离
type MinHeap [][3]int
 
func (h MinHeap) Len() int {
	return len(h)
}
 
func (h MinHeap) Less(i, j int) bool {
	return h[i][2] < h[j][2]
}
 
func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}
 
func (h *MinHeap) Push(v any) {
	*h = append(*h, v.([3]int))
}
 
func (h *MinHeap) Pop() any {
	n := len(*h)
	res := (*h)[n-1]
	*h = (*h)[:n-1]
	return res
}
 
const (
	MAXN       = 100
	TEST_TIMES = 10000
)
 
func main() {
	fmt.Print("正确性证明：")
	for i := 0; i < TEST_TIMES; i++ {
		n := rand.Intn(MAXN) + 2
		grid := randomGrid(n)
		startX := rand.Intn(n)
		startY := rand.Intn(n)
		endX := rand.Intn(n)
		endY := rand.Intn(n)
		ans0 := minDistance0(grid, startX, startY, endX, endY)
		ans1 := minDistance1(grid, startX, startY, endX, endY)
		ans2 := minDistance2(grid, startX, startY, endX, endY, f1)
		if ans0 != ans1 || ans0 != ans2 {
			panic("错误")
		}
	}
	fmt.Println("正确")
 
	fmt.Println("速度测试：")
	grid := randomGrid(4000)
	startX := 0
	startY := 0
	endX := 3900
	endY := 3900
	start := time.Now()
	ans0 := minDistance0(grid, startX, startY, endX, endY)
	elapsed := time.Since(start)
	fmt.Println("普通 bfs：", elapsed)
	start = time.Now()
	ans1 := minDistance1(grid, startX, startY, endX, endY)
	elapsed = time.Since(start)
	fmt.Println("Dijkstra 算法：", elapsed)
	start = time.Now()
	ans2 := minDistance2(grid, startX, startY, endX, endY, f1)
	elapsed = time.Since(start)
	fmt.Println("A* 算法-曼哈顿距离：", elapsed)
	start = time.Now()
	ans3 := minDistance2(grid, startX, startY, endX, endY, f2)
	elapsed = time.Since(start)
	fmt.Println("A* 算法-对角线距离：", elapsed)
	if ans0 != ans1 || ans2 != ans3 || ans0 != ans2 {
		fmt.Println(ans0, ans1, ans2, ans3)
		panic("error")
	}
}
 
func randomGrid(n int) [][]int {
	grid := make([][]int, n)
	r := 0
	for i := 0; i < n; i++ {
		grid[i] = make([]int, n)
		for j := 0; j < n; j++ {
			r = rand.Intn(10)
			if r < 3 {
				// 每个格子有 30% 概率是 0
				grid[i][j] = 0
			} else {
				// 每个格子有 70% 概率是 1
				grid[i][j] = 1
			}
		}
	}
	return grid
}
 
func abs(v int) int {
	if v < 0 {
		return -v
	}
	return v
}

正确性证明：正确
速度测试：
普通 bfs： 704.233121ms
Dijkstra 算法： 3.197619676s
A* 算法-曼哈顿距离： 294.078491ms
A* 算法-对角线距离： 2.878733403s

总结 §

这个问题可以用普通 bfs 来解决、Dijkstra 来解决、A* 来解决

Dijkstra 比普通 bfs 多了个堆，时间复杂度还多了 $lo{g}^n$ 的堆操作

A* 和 Dijkstra 的时间复杂度是一样的，只是优化了常数时间，预估距离越接近真实最短距离，优化的常数时间越多（这道题曼哈顿距离比对角线距离更快）

但是要注意保证预估距离 <= 真实最短距离，否则答案是错误的！（比如这道题如果可以走斜线，那么曼哈顿距离就是错的）

Floyd 算法 §

弗洛伊德算法

得到图中任意两点之间的最短距离

适用于任何图，不管有向无向、不管边权正负、但是不能有负环（保证最短路存在）

负环：有一个环，环中权重和为负。一直转圈，最短路一直变小，相当于最短路是负无穷

过程简述：

遍历所有点作为跳板点，以每一个跳板点遍历一个点到另一个点的距离，看经过跳板点能不能让距离变小

distance[i][j] 表示 i 和 j 之间的最短距离

distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

枚举所有的 k（跳板点）即可，实现时一定要最先枚举跳板！

时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$，常数时间小，容易实现（$n$ 为点数）

题目1.Floyd 算法模版 §

测试链接 §

P2910【USACO08OPEN】Clear And Present Danger S

答案 §

package main
 
import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)
 
const (
	MAXN    = 101
	MAXM    = 10001
	MAX_INT = math.MaxInt
)
 
var (
	n        int
	m        int
	path     = [MAXM]int{}
	distance = [MAXN][MAXN]int{}
)
 
func floyd() {
	// O(n^3) 的过程
	// 枚举每个跳板
	// 注意，跳板要最先枚举！
	for bridge := 0; bridge < n; bridge++ { // 跳板
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if distance[i][bridge] != MAX_INT &&
					distance[bridge][j] != MAX_INT &&
					distance[i][j] > distance[i][bridge]+distance[bridge][j] {
					distance[i][j] = distance[i][bridge] + distance[bridge][j]
				}
			}
		}
	}
}
 
func main() {
	// s := `3 4
	// 1
	// 2
	// 1
	// 3
	// 0 5 1
	// 5 0 2
	// 1 2 0`
	// in := bufio.NewScanner(strings.NewReader(s))
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		m, _ = strconv.Atoi(in.Text())
		for i := 0; i < m; i++ {
			in.Scan()
			path[i], _ = strconv.Atoi(in.Text())
			path[i]--
		}
		// 这道题给的图是邻接矩阵的形式
		// 任意两点之间的边权都会给定
		// 所以显得 distance 初始化不太必要
		// 但是一般情况下，distance 初始化一定要做
		// for i := 0; i < n; i++ {
		// 	for j := 0; j < n; j++ {
		// 		distance[i][j] = MAX_INT
		// 	}
		// }
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				in.Scan()
				distance[i][j], _ = strconv.Atoi(in.Text())
			}
		}
		floyd()
		ans := 0
		for i := 1; i < m; i++ {
			ans += distance[path[i-1]][path[i]]
		}
		fmt.Fprintln(out, ans)
	}
	out.Flush()
}

Bellman-Ford 算法 §

贝尔曼-福德算法

解决可以有负权边但是不能有负环（保证最短路存在）的图，单源最短路算法（给定一个源点，求解从源点到每个点的最短路径长度。）

和 Dijkstra 算法 是解决同样的问题，但可以有权重为负的边

松弛操作：

• 假设源点为 A，从 A 到任意点 F 的最短距离为 distance[F]
• 假设从点 P 出发某条边，去往点 S，边权为 W
• 如果发现，distance[P] + W < distance[S]，也就是通过该边可以让 distance[S] 变小
• 那么就说，P 出发的这条边对点 S 进行了松弛操作

Bellman-Ford 过程：

1. 每一轮考察每条边，每条边都尝试进行松弛操作，那么若干点的 distance 会变小
2. 当某一轮发现不再有松弛操作出现时，算法停止

Bellman-Ford 算法时间复杂度：

• 假设点的数量为 N，边的数量为 M，每一轮时间复杂度 O(M)
• 最短路存在的情况下，因为 1 次松弛操作会使 1 个点的最短路的边数 +1
• 而从源点出发到任何点的最短路最多走过全部的 n 个点，所以松弛的轮数必然 <= n - 1
• 所以 Bellman-Ford 算法时间复杂度 O(M*N)

重要推广：判断从某个点出发能不能到达负环

• 上面已经说了，如果从 A 出发存在最短路（没有负环），那么松弛的轮数必然 <= n - 1
• 而如果从 A 点出发到达一个负环，那么松弛操作显然会无休止地进行下去
• 所以，如果发现从 A 点出发，在第 n 轮时松弛操作依然存在，说明从 A 点出发能够到达一个负环

题目1.Bellman-Ford 算法应用 §

不是 Bellman-Ford 模版，下面这道题 才是模板，这个是 Bellman-Ford 算法应用，是一个阉割版

题目描述 §

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei]，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

提示：

• 1 <= n <= 100
• 0 <= flights.length <= (n * (n - 1) / 2)
• flights[i].length == 3
• 0 <= fromi, toi < n
• fromi != toi
• 1 <= pricei <= 10^4
• 航班没有重复，且不存在自环
• 0 <= src, dst, k < n
• src != dst

测试链接 §

787.K 站中转内最便宜的航班

答案 §

const (
	MAX_INT = math.MaxInt
)
 
// Bellman-Ford 算法
// 针对此题改写了松弛逻辑
func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
	cur := make([]int, n)
	for i := range cur {
		cur[i] = MAX_INT
	}
	cur[src] = 0
	for i := 0; i <= k; i++ { // 松弛的轮数是 k 轮
		// 这道题 Bellman-Ford 的松弛轮数和航班中转次数对不上
		// 一轮松弛可能导致多次中转（对多个节点进行松弛）
		// 所以要阉割 Bellman-Ford，使得 Bellman-Ford 一轮只中转一次
		// 具体做法就是每轮松弛时从旧的 distance 中取距离进行判断
		next := make([]int, n)
		copy(next, cur)
		for _, edge := range flights {
			// 从旧的 distance 进行判断
			// 从当前 distance 进行判断的话一轮可能会更新多个节点的 distance
			// 就和航班中转次数对不上了
			// 阉割成一轮只更新一个节点的 distance
			if cur[edge[0]] != MAX_INT {
				next[edge[1]] = min(next[edge[1]], cur[edge[0]]+edge[2])
			}
		}
		cur = next
	}
	if cur[dst] == MAX_INT {
		return -1
	}
	return cur[dst]
}

SPFA 优化 Bellman-Ford §

SPFA：Shortest Path Faster Algorithm，最短路径加速算法

很轻易就能发现，每一轮考察所有的边看看能否做松弛操作是不必要的。因为只有上一次被某条边松弛过的节点，所连接的边，才有可能引起下一次的松弛操作

所以用队列来维护“这一轮哪些节点的 distance 变小了”，下一轮只需要对这些点的所有边，考察有没有松弛操作即可

网上说，SPFA 已死。有时候死了，有时候诈尸了，称为薛定谔的 SPFA，这是啥意思？

是因为题目的测试用例更专业，SPFA 只优化了常数时间，在大多数情况下跑得很快，但时间复杂度仍然为 $O(n\ast m)$

看复杂度就知道只适用于小图，根据数据量谨慎使用，在没有负权边时要使用 Dijkstra 算法

所以，在数据量允许的时候使用，数据量不允许的情况下就不能用（会超时）

Bellman-Ford + SPFA 优化的用途：

1. 适用于小图
2. 解决有负边（没有负环）的图的单源最短路径问题，没有负边用 Dijkstra 算法 更优
3. 可以判断从某个点出发是否能遇到负环
   • 如果想判断整张有向图有没有负环，需要设置虚拟源点
   • 虚拟一个源点，其到所有点的权重为 0 即可
4. 并行计算时会有很大优势，因为每一轮多点判断松弛操作是相互独立的，可以交给多线程处理
   • 笔面试、比赛只考虑单 CPU 单线程，用不到
   • 实际工程中可以考虑

备注：

SPFA 的另一个重要的用途是解决“费用流”问题，当然也可以被 Primal-Dual 原始对偶算法替代

这一内容会在【挺难】标签下的课程里讲述

“费用流”问题在大厂笔试、面试中是冷门内容，但是致力于比赛的同学是必须要掌握的

题目1.Bellman-Ford + SPFA 优化模版 §

Bellman-Ford + SPFA 优化模版 + 判断负环

题目描述 §

给定一个 n 个点的有向图，请求出图中是否存在从顶点 1 出发能到达的负环。

负环的定义是：一条边权之和为负数的回路。

输入格式：

输入的第一行是一个整数 T，表示测试数据的组数。对于每组数据的格式如下：

第一行有两个整数，分别表示图的点数 n 和接下来给出边信息的条数 m。

接下来 m 行，每行三个整数 u、v、w。

• 若 w≥0，则表示存在一条从 u 至 v 边权为 w 的边，还存在一条从 v 至 u 边权为 w 的边。
• 若 w<0，则只表示存在一条从 u 至 v 边权为 w 的边。

输出格式：

对于每组数据，输出一行一个字符串，若所求负环存在，则输出 YES，否则输出 NO。

测试链接 §

P3385【模板】负环

答案 §

package main
 
import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)
 
const (
	MAXN    = 2001
	MAXM    = 6001
	MAXQ    = 4000001 // SPFA 需要
	MAX_INT = math.MaxInt
)
 
var (
	n int
	m int
 
	head   = [MAXN]int{}
	next   = [MAXM]int{}
	to     = [MAXM]int{}
	weight = [MAXM]int{}
	cnt    = 1
 
	distance  = [MAXN]int{} // 源点出发到每个节点的距离表
	updateCnt = [MAXN]int{} //节点被松弛的次数，用于判断负环
	queue     = [MAXQ]int{} // SPFA: 哪些节点被松弛了放入队列
	h, t      = 0, 0
	enter     = [MAXN]bool{} // 节点是否已经在队列中
)
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	in.Scan()
	t, _ := strconv.Atoi(in.Text())
	for ; t > 0; t-- {
		in.Scan()
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		m, _ = strconv.Atoi(in.Text())
		build()
		u, v, w := 0, 0, 0
		for i := 0; i < m; i++ {
			in.Scan()
			u, _ = strconv.Atoi(in.Text())
			in.Scan()
			v, _ = strconv.Atoi(in.Text())
			in.Scan()
			w, _ = strconv.Atoi(in.Text())
			if w >= 0 {
				addEdge(u, v, w)
				addEdge(v, u, w)
			} else {
				addEdge(u, v, w)
			}
		}
		if spfa() {
			fmt.Fprintln(out, "YES")
		} else {
			fmt.Fprintln(out, "NO")
		}
	}
	out.Flush()
}
 
func build() {
	cnt = 1
	h, t = 0, 0
	for i := 1; i <= n; i++ {
		head[i] = 0
		distance[i] = MAX_INT
		updateCnt[i] = 0
		enter[i] = false
	}
}
 
func addEdge(f, t, w int) {
	next[cnt] = head[f]
	to[cnt] = t
	weight[cnt] = w
	head[f] = cnt
	cnt++
}
 
func spfa() bool {
	distance[1] = 0
	updateCnt[1]++
	queue[t] = 1
	t++
	enter[1] = true
	for h < t { // 队列不为空，即：还有节点正在松弛
		u := queue[h]
		h++
		enter[u] = false
		for i := head[u]; i > 0; i = next[i] {
			v := to[i]
			w := weight[i]
			if distance[u]+w < distance[v] {
				distance[v] = distance[u] + w
				if !enter[v] {
					if updateCnt[v] == n { // 松弛了 n 轮还能松弛，说明有负环
						return true
					}
					updateCnt[v]++
					queue[t] = v
					t++
					enter[v] = true
				}
			}
		}
	}
	return false
}