01 BFS
概要
辺の長さが 0 または 1 である (各ノード間のコストが 0 または 1) である 有向グラフ において、ある 1 つの始点から全頂点への最短経路を効率よく求めることができる。
通常の BFS でも可能だが 01-BFS はより効率的に解くことができる。
ダイクストラ法のように辺の長さが 非負 である有向グラフでは探索候補の中で 暫定最短距離が最も小さい頂点 を選び探索を進めていく。辺の長さがすべて非負の有向グラフにおいては経路が進むことで始点からの合計距離が減ることが無いため、各ステップにおいて「暫定最短距離が最も小さい頂点」は 真の最短距離 になっていることが保証される。つまり 暫定最短距離が最も小さい頂点 を優先して探索することで 2 度手間をなくし効率化している。
これは BFS においても同様で探索候補をキューに入れる際に下記のように優先付けを行い、暫定最短距離が小さい頂点から優先的に探索を行うようにする。
- 辺の長さが 0 の時はキューの 先頭 に追加する
- 辺の長さが 1 の時はキューの 末尾 に追加する
計算量
頂点数 \(V\)、辺数 \(E\) の時 \(O(V+E)\)