算法之美：BFS破解多源最短径路
目录
前言
在图论与网格相关的问题里，最常见的一类就是求取最短距离。一般来说，我们会从某一个起始点出发，借助BFS（广度优先搜索）逐层去拓展，从而得到从该点到所有其他点的最短路径。然而，在诸多实际场景中，往往存在多个起始点：例如多个水源向四周扩展到所有陆地、多个火源蔓延到整片森林，又或者像LeetCode 1162. 地图分析中，从所有陆地出发，计算到最远海洋的距离。这类问题的核心思想就是BFS多源最短路。它和单源BFS的不同之处在于：
– 把所有的起点一开始就一块加入队列，当作BFS的第一层；
– 在层层拓展的过程中，天然就能保证最短路径的正确性；
– 代码实现起来非常简洁，不需要进行多次额外的BFS。
前提引入
- 图可以是有方向的也可以是无方向的；边可以带有权重（比如花费、距离、时间等）。
- 最短路：从A点到B点的最小代价之和。
常见的几种场景：
1. 单源最短路（SSSP）：从一个起点s到所有点的最短路径。
2. 多源最短路（有两种含义）：
– 多起点→所有点：有好几个起点，一起“向外扩散”；
– 任意两点（全源/全对，APSP）：所有点到所有点的最短路径。
多源最短路的两种玩法：
– 多起点→所有点（常见于“多个出发点最近距离”）
– 无权图：把所有起点一块入队，进行一次BFS（上面的bfs_multi_source就是这样）。
– 有权非负：把所有起点的距离设为0，一块入堆，进行一次Dijkstra算法。
– 有负边：添加一个超级源点S，向每个起点连一条权重为0的边，然后用Bellman–Ford或者其他方案。
谈谈多源最短路
如何解决：1. 暴力方法，把多源最短路问题转换成若干个单元最短路问题，大概率会超时；2.把所有的源点当作一个“超级源点”，这样问题就变成了单一的单源最短路问题
从理性角度需要严谨的证明，从感性理解来看，就是多个起点出发，向外扩展的时候，舍弃较差的情况，选取更优的情况。在代码层面，把所有的起点加入到队列里面，一层一层地向外拓展。
题目实练
矩阵
给定一个由0和1组成的矩阵mat，需要输出一个大小相同的矩阵，其中每个格子是mat中对应位置元素到最近的0的距离。两个相邻元素间的距离为1。
1. 一个一个位置去求，每个位置都来一趟BFS，这样做大概率会超时。
2. 多源BFS+正难则反，把所有的0当作起点，1当作终点，这样1的位置就直接填上结果，按照原先1找0的思路倒推写值。把所有的0加入到队列中，一层一层地向外拓展就行。
class Solution {
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int n=mat.size(),m=mat[0].size();
vector<vector<int>> dict(n,vector<int>(m,-1));
queue<pair<int,int>>q;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mat[i][j]==0){
q.push({i,j});
dict[i][j]=0;
}
}
}
while(q.size()){
auto[a,b]=q.front();
q.pop();
for(int i=0;i<4;i++){
int x=a+dx[i];
int y=b+dy[i];
if(x>=0 && x<n && y>=0 && y<m && dict[x][y]==-1){
dict[x][y]=dict[a][b]+1;
q.push({x,y});
}
}
}
return dict;
}
};
飞地的数量
给你一个大小为m x n的二进制矩阵grid，其中0表示一个海洋单元格、1表示一个陆地单元格。一次移动是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过grid的边界。返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。
核心思想：反向思考
与其找“飞地”，不如先把能连到边界的陆地标记掉。剩下的没标记的陆地，就是飞地。
实现步骤
1. 从边界出发，把所有相连的陆地用BFS/DFS标记
2. 遍历整个网格，统计没被标记的陆地数量
class Solution {
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
public:
int numEnclaves(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size();
vector<vector<bool>>vis(m,vector<bool>(n));
queue<pair<int,int>>q;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==0 || i==m-1 || j==0 || j==n-1){
if(grid[i][j]==1){
q.push({i,j});
vis[i][j]=true;
}
}
}
}
while(q.size()){
auto [a,b]=q.front();
q.pop();
for(int i=0;i<4;i++){
int x=a+dx[i];
int y=b+dy[i];
if(x>=0 && x<m && y>=0 && y<n && grid[x][y]==1 && !vis[x][y]){
q.push({x,y});
vis[x][y]=true;
}
}
}
int num=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j] && !vis[i][j])
num++;
}
}
return num;
}
};
BFS遍历时，从边界所有1出发，把能到达的全部标记。最终只数没被标记的陆地，就是飞地。
地图中的最高点
给你一个大小为m x n的整数矩阵isWater，它代表了一个由陆地和水域单元格组成的地图。
– 如果isWater[i][j] == 0，格子(i, j)是一个陆地格子。
– 如果isWater[i][j] == 1，格子(i, j)是一个水域格子。
需要按照如下规则给每个单元格安排高度：
– 每个格子的高度都必须是非负的。
– 如果一个格子是水域，那么它的高度必须为0。
– 任意相邻的格子高度差至多为1。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）
找到一种安排高度的方案，使得矩阵中的最高高度值最大。请你返回一个大小为m x n的整数矩阵height，其中height[i][j]是格子(i, j)的高度。如果有多种解法，请返回任意一个。
本题就是第一个练习题的变式
class Solution {
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
public:
vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
int n=isWater.size(),m=isWater[0].size();
vector<vector<int>> vis(n,vector<int>(m,-1));
queue<pair<int,int>> q;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(isWater[i][j]==1){
vis[i][j]=0;
q.push({i,j});
}
}
while(q.size()){
auto[a,b]=q.front();
q.pop();
for(int i=0;i<4;i++){
int x=a+dx[i];
int y=b+dy[i];
if(x>=0 && x<n && y>=0 && y<m && vis[x][y]==-1){
vis[x][y]=vis[a][b]+1;
q.push({x,y});
}
}
}
return vis;
}
};
地图分析
你现在手里有一份大小为n x n的网格grid，上面的每个单元格都用0和1标记好了。其中0代表海洋，1代表陆地。请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回-1。我们这里说的距离是「曼哈顿距离」（Manhattan Distance）：(x0, y0)和(x1, y1)这两个单元格之间的距离是|x0 - x1| + |y0 - y1|。
题目要找：每个海洋格子到最近陆地的距离的最大值。这就是一个典型的最短路到最近源点的问题：如果把所有陆地当作“源点”，那么每个海洋格子的最短距离就是从这些源点出发的BFS层数。
核心思路（多源 BFS）
1. 把所有陆地(1)同时入队
– 建一个queue<pair<int,int>> q。
– 建一个距离/访问数组vis，初值都为-1（表示未访问/未知距离）。
– 遍历网格，若grid[i][j]==1，则vis[i][j]=0，并q.push({i,j})。这样就等价于从所有陆地同时作为起点，向四周一圈一圈地扩散。
2. 从陆地向外层层扩散（BFS）
– 出队一个格子(a,b)，尝试4个方向(x,y)。
– 若(x,y)没越界、且vis[x][y]==-1（还没确定过距离），就设vis[x][y]=vis[a][b]+1，把(x,y)入队。这一步保证了第一次到达某海洋格子时走的是最短路径（BFS性质）。
3. 记录答案
– 在给某个新格子赋值vis[x][y]=vis[a][b]+1的同时，用ret=max(ret, vis[x][y])维护目前最大的距离。
– BFS完毕后返回ret。
为什么不用额外写两种边界判断
– 全是海洋：初始队列为空，while(q.size())不执行，ret保持-1，直接返回-1 ✅
– 全是陆地：所有陆地进队，但周围没有“未访问的海洋”可扩展，ret从头到尾未更新，仍为-1，返回-1 ✅
– 既有陆地也有海洋：扩散会把海洋逐层更新，ret会被更新到最大层数（最远的海洋到最近陆地的距离）✅
BFS从所有陆地同时出发，按“层”向外扩展。第一次访问到的海洋格子，其层数就是它到最近陆地的最短步数；后来再访问到它的路径只会更长，不会更短。于是每个海洋的vis值都恰好是到最近陆地的距离。最大值自然是题目要的答案。
结束语
BFS多源最短路的关键，在于利用队列并行扩展所有起点，避免了重复计算，也保证了结果的全局最优。它是BFS思想在实际问题中的一种高效变形，常见于网格扩散、距离计算、最短传播路径等题型中。掌握这种方法后，你会发现：只要问题中存在“从一批点出发、寻找离它们最远或最近的点”的场景，往往都能一眼识别出是多源BFS的典型应用。
相关文章
