0-1 bfs 的正确性证明
发现以前没想明白,今天证一下。
只要证明队列里的 dis 是单调不降的就好了。
证明队列里的 dis 是形如 \(\{d,d,\dots,d,d+1,\dots,d+1\}\):
- 初始为 \(\{0\}\)。
- 队头为 \(u\)。边权 \(w=0\) 时,\(dis_v=d\),放在队头符合;边权 \(w=1\) 时,\(dis_v=d+1\),放在队尾符合。
发现以前没想明白,今天证一下。
只要证明队列里的 dis 是单调不降的就好了。
证明队列里的 dis 是形如 \(\{d,d,\dots,d,d+1,\dots,d+1\}\):