バグの発生しないBFSの書き方

次の3つのルールを守る。

• キューに追加する直前に、まだ距離配列が更新されていないかをチェックする
• キューに追加するときに距離配列を更新する
• それ以外の場所で距離配列をチェックしたり、更新したりしない

このルールを守ることで、シンプルかつバグの発生しないコードが書ける。

queue<int> q;
q.push(0);
dist[0] = 0;
while (!q.empty()) {
  int u = q.front(); q.pop();
  for (auto v : edges[u]) {
    if (dist[v] != INVALID) continue;
    q.push(v);
    dist[v] = dist[u] + 1;
  }
}