01bfs

Clyth · 2025-10-20 09:03:52 · 算法·理论

定义

在边权为0或1的图上求最短路的bfs。

解释

01bfs其实就是一个图上最短路的算法，解决在边权只有0或1时的问题，在这种情况下，它比dijkstra和spfa更加快速且稳定。

算法的整体框架与dijkstra类似，运用贪心的思想。

如果边权为 0，我们希望更快到达，应该优先处理。 如果边权为 1，代价高一点，就可以稍后处理。

这样就能保证更短路径更优先被遍历，维护了最短路径的拓展顺序,每个状态在第一次出队是就是当前的最优解。

这其实就是用deque中的顺序，模拟了dijkstra中优先队列中「更小代价优先」的行为，而且相比其而言，使用deque维护的时间复杂度是O(1)的。

时间复杂度

每条边最多被访问一次：O(M)

每个点最多入队一次：O(N)

总复杂度：O(N+M)——比dijkstra的O((N+M)logN)更快。

应用范围

边权全为1：朴素bfs O(N+M)

边权为0或1: 01bfs O(N+M)

边权随机：dijkstra或spfa O((N+M)logN)

例题讲解

P4554 小明的游戏

给定一个 n×m 的棋盘，上面有两种格子 # 和 @。游戏的规则很简单：给定一个起始位置和一个目标位置，小明每一步能向上，下，左，右四个方向移动一格。如果移动到同一类型的格子，则费用是 0，否则费用是 1。请编程计算从起始位置移动到目标位置的最小花费。

题目思路：

其实没什么好分析的...“如果移动到同一类型的格子，则费用是 0，否则费用是 1”这句话就说明的这道题能用01bfs，那么直接套模板就行了

#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,ex,ey;
char c[505][505];
struct node{
    int x,y,d;
};
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int  dis[505][505];
void bfs(){
    memset(dis,0x3f,sizeof dis);
    deque<node> q;
    q.push_front({sx,sy,0});
    dis[sx][sy]=0;
    while(!q.empty()){
        node t=q.front();q.pop_front();
        int x=t.x,y=t.y;
        //到达目标点
        if(x==ex&&y==ey){
            cout<<t.d<<'\n';
            return;
        }
        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;
            int nd=t.d+(c[x][y]!=c[nx][ny]);
            if(nd<dis[nx][ny]){//类似于dijkstra的“松弛”操作
                dis[nx][ny]=nd;
                //如果代价是0就放入队首，代价是1就放入队尾
                if(c[x][y]==c[nx][ny]) q.push_front({nx,ny,nd});
                else q.push_back({nx,ny,nd});
            }
        }
    }
}
int main(){
    while(cin>>n>>m){
        if(n==0&&m==0) break;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>c[i][j];
            }
        }
        cin>>sx>>sy>>ex>>ey;
        bfs();
    }
    return 0;
}

其实其他的题目不想这道题这么板，边权是0或1的条件一般都隐藏在题意中，需要分析去发现。

推荐题目:
CF1749E Cactus Wall
AT_abc213_e [ABC213E] Stronger Takahashi
UVA11573 Ocean Currents