算法提高课汇总

单源$BFS$正确性证明

单源$BFS$应用在求边权相等且边权大于0的图中的单源最短路问题.

证明思路是首先证明在$BFS$中普通的队列等价于单调队列, 接着可用
类似$Dijkstra$算法的证明思路证明. 下面证明过程中假设图中权值均为1.

队列的性质

证明队列具有:

• 两段性 — 每个时刻队列中顶点距离最多有$2$个值, 且两个值相差为$1$.

• 单调性 — 队列中顶点距离非严格单调递增, 即前面连续一段值均为$x$,
  后面连续一段值最大为$x + 1$.

证明: 数学归纳法

1. 初始时, 队列中只有起点, 距离为$0$. 满足上述两个性质.

2. 假设第$k$步时, 队列中数值为$x, …, x, x + 1, …, x + 1$.
   则第$k + 1$步时, 取出队头节点$u$, 将$u$相邻且还未被访问节点加入队尾,
   距离均为$x + 1$. 此时队列仍然满足上述两个性质.

$Dijkstra$思路证明

我们已经证明$BFS$中的队列等价于单调队列, 此时算法过程等价于堆优化的$Dijkstra$算法.

不过两者仍有一点不同: $Dijkstra$算法中, 顶点$u$出队时的最小值为全局最小值, 而$BFS$入队时
即为全局最小值. 原因是$BFS$应用在边权相等的图中.

下面证明$BFS$算法中入队时即确定顶点的全局最小值.

证明: 反证法

假设对于顶点$u$, 其第一次入队时距离为$x$, 此时$x$不是全局最小值.

即$x$会被后续节点更新为$x’$, 且$x’\lt x$.

由于队列具有单调性, 后续节点的距离$d\ge x$, 而后续节点至少经过1步走到$u$,
所以$x’\ge x + 1$, 与假设矛盾.

题意理解

求每个顶点到所有1最小距离的全局最小值. 一种思路是将每个1作为起点
每次执行一次单源$BFS$. 时间复杂度$O(n^4)$.

本题可以视为有限个起点的单源最短路问题, 参考 AcWing 1137. 选择最佳线路 ,
可建立虚拟源点, 将问题转化为单源$BFS$问题.

具体实现

实现时可建立虚拟源点$s$, 向每个点连一条边权为0的边.

为了满足$BFS$边权相等的要求, 以及代码的方便实现: 上述思路实际等价于先将所有1的顶点入队,
距离赋值为0. 即省去建立虚拟源点的步骤.

实现代码 $O(n^2)$

#include <cstring>
#include <iostream>

#define x first
#define y second

using namespace std;

typedef pair<int, int> pii;

const int N = 1010;

int n, m;
int dist[N][N];
pii q[N * N];
char g[N][N];

void bfs()
{
    int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

    memset(dist, -1, sizeof dist);
    int tt = 0, hh = 0;
    for( int i = 0; i < n; i ++ )
        for( int j = 0; j < m; j ++ )
            if( g[i][j] == '1' )
            {
                dist[i][j] = 0;
                q[tt ++] = {i, j};
            }

    while( hh < tt )
    {
        pii cur = q[hh ++];
        int x = cur.x, y = cur.y;
        for( int i = 0; i < 4; i ++ )
        {
            int nx = x + dx[i], ny = y + dy[i];
            if( nx < 0 || nx >= n || ny < 0 || ny >= m )    continue;
            if( dist[nx][ny] != -1 )    continue;

            dist[nx][ny] = dist[x][y] + 1;
            q[tt ++] = {nx, ny};
        }
    }
}

int main()
{
    cin >> n >> m;
    for( int i = 0; i < n; i ++ )   cin >> g[i];

    bfs();

    for( int i = 0; i < n; i ++ )
    {
        for( int j = 0; j < m; j ++ )
            cout << dist[i][j] << ' ';
        cout << endl;
    }

    return 0;
}