多源BFS问题

前言:
本文的是对多源起点求最短距离问题 的分析，

需要先了解单源最短路问题，博文如下:

BFS之最短路径_Dream.Luffy的博客-CSDN博客

例题如下：

矩阵距离

给定一个 N 行 M 列的 01 矩阵 A，A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为：

dist(A[i][j],A[k][l])=|i−k|+|j−l|

输出一个 N 行 M 列的整数矩阵 B，其中：

B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])

第一行两个整数 N,M。

接下来一个 N 行 M 列的 01 矩阵，数字之间没有空格。

输出格式

一个 N 行 M 列的矩阵 B，相邻两个整数之间用一个空格隔开。

数据范围

1≤N,M≤1000

输入样例：

3 4
0001
0011
0110

输出样例：

3 2 1 0
2 1 0 0
1 0 0 1

算法分析：

转换题意，本题求的是每个0 距离所有的1的最短距离。

如果我们分别以每一个1为起点，遍历整个矩阵保留最小值，这时时间复杂度将是O(n^2)级别，

在FloodFill算法中，时间复杂度是O(n^2)级别, 而现在存在多个起点，假设有n2/2" role="presentation">n2/2$n^2/2$个 起点和n2/2" role="presentation">n2/2$n^2/2$

个空地，那么时间复杂度将达到O(n^4) ,  那么我们就需要一个优化

可以将本题看作一道有多个起始状态的Flood Fill。 将每个1都看作起点

对于每个位置，从任意一个起点出发的情况下，求到达该位置所需要的最小步数。

        对于这种具有多个等价起点的起始状态的问题中， 我们只需要在BFS时，把这些起始状态全部插入队列，而根据Flood fill算法逐层搜索的性质，每个位置第一次被访问时，就相当于距离它最近的起点扩展到了它。

例图：

正确性证明：

要证明该算法正确性，则需要证明队列q具有

① 二段性

② 单调性

具体证法与FloodFill算法类似，这里不再赘述 

我们可以借助图论的思想， 将它转换为单源最短路问题：添加一个虚拟源点，令所有起点与该源点的边权为0，那么也就相当于求单源最短路问题。

coding:

//多源最短路问题， 求一个点距离所有源点中路径最短的距离
#include
#include
#include
 
#define x first
#define y second
 
using namespace std;
 
typedef pair<int,int> PII;
 
const int N = 1010, M = N * N;
 
int n, m;
char g[N][N]; //因为输入没有空格，所以要用字符读入
PII q[M];
int dist[N][N];
 
 
void bfs()
{
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    memset(dist, -1, sizeof dist);
    
    int hh = 0, tt = -1; //这里有很多起点，所以不用q[hh ++], 而都是q[tt ++]所以tt = -1
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            if(g[i][j] == '1') //是1则入队
            {
                dist[i][j] = 0;
                q[ ++ tt] = {i, j};
            }
    
    while(hh <= tt)
    {
        PII t = q[hh ++];
        
        for(int i = 0;i < 4;i ++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a < 1 || a > n || b < 1 || b > m) continue;
            if(dist[a][b] != -1) continue;
            
            dist[a][b] = dist[t.x][t.y] + 1;
            q[ ++ tt] = {a, b};
        }
    }
}
 
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;i ++ ) scanf("%s", g[i] + 1);
    
    bfs();
    //打印每个点的最短距离
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++) printf("%d ",dist[i][j]);
        cout << endl;
    }
}

希望本文对你有帮助

该系列会持续更新, 我是Luffy，期待与你再次相遇