0-1 BFS: 一种特殊情况下的最短路算法
0-1 BFS: 一种特殊情况下的最短路算法
什么是 0-1 BFS 算法
这是用于解决边权只有 $0$ 或 $1$ 的图上的 单源最短路径算法。它的优势在于它可以在 $O(V+E)$ 的时间复杂度内，计算特定图的最短路。
思想
该算法实际上是基于 堆优化的 Dijkstra 单源最短路径算法 的一种优化。Dijkstra 的基本思想是查询 当前最短路径顶点 $u$，通过 松弛 操作，更新所有 $\forall v,(u, v) \in E$ 的结果。堆优化实际上优化了查询 当前最短路径顶点 的时间复杂度。
如果图 $G$ 的所有边权只有 $0$ 或 $1$，对于 当前最短路径顶点 $u$，如果 $v$ 可以被 松弛:
- 如果 $e_{(u,v)}=0$，那么 $d_v=d_u+e_{(u,v)}$ 一定是最优的
- 如果 $e_{(u,v)}=1$，那么 $d_v=d_u+e_{(u,v)}$ 可能是最优的
因此，我们也不必通过 堆 来维护 当前最短路径顶点 的信息了。可以通过 双端队列 实现 $O(1)$ 维护最小值：
- 队头 代表 当前最短路径顶点
- 如果 $e_{(u,v)}=0$，把顶点放到 队头
- 如果 $e_{(u,v)}=1$，把顶点放到 队尾
从而成功的省掉一个 $log(n)$，将时间复杂度降到了 $O(V+E)$。
6081. 到达角落需要移除障碍物的最小数目
0-1 BFS 模板题
class Solution {
public:
int minimumObstacles(vector<vector<int>> &grid) {
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int n = grid.size();
int m = grid[0].size();
auto dis = vector<int>(n * m, 2 * n * m);
auto used = vector<char>(n * m);
deque<int> dq;
dis[0] = 0;
dq.emplace_back(0);
while (!dq.empty()) {
int id = dq.front();
dq.pop_front();
int x = id / m;
int y = id % m;
if (used[id]) continue;
used[id] = true;
for (int i = 0; i < 4; ++i) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
if (used[xx * m + yy]) continue;
if (dis[id] + grid[x][y] < dis[xx * m + yy]) {
dis[xx * m + yy] = dis[id] + grid[x][y];
if (grid[x][y]) dq.emplace_back(xx * m + yy);
else dq.emplace_front(xx * m + yy);
}
}
}
return dis.back();
}
};