BFS variants: multi-source, 0-1 BFS, zero-cost moves, reverse graph
- Stage
- 5
- Module
- M5.9
- Lessons
- 1
In this module
- Implement multi-source BFS starting from several nodes at once.
- Use 0-1 BFS with deque to handle graphs with edge weights 0 and 1.
- Detect and process forced zero-cost moves (conveyors) with cycle detection.
- Apply reverse-graph BFS to find distances backward from a target.
Before this module
Lessons
Practice
Try these on the judges. Each link opens the problem on WMOJ or DMOJ.
- 2018 S3RoboThieves (opens on DMOJ in a new tab) DMOJ
Search from multiple starting positions while handling conveyors and cameras.
Why DMOJ: Combines multi-source BFS with zero-cost-move detection.
- 2021 S4Daily Commute (opens on WMOJ in a new tab) WMOJ
Find optimal daily routes using per-day BFS with reverse-graph distances.