ビビジランテソンテネグロホメストーニカルマンドーレポポス

さあ、いつまでたってもオレンジコーダーになれない子はどんどんしまっちゃおうねー

多点BFS 解説

はじめに

「多点BFS」でググったときに出てくる一番まともな解説が僕のツイートであることに危機感を覚えたので（雑な）解説記事を書くことにしました。 （ツイ消ししてしまう可能性があるので）

多点BFS とは

通常のBFSを、さらに始点が複数になっても扱えるように拡張したものが多点BFSです。
「始点が複数あって、各終点に対してそれぞれの始点との最短距離を計算した上でそれらの最短距離の最小値を求めたい」みたいなときに使います。
英語だと、multi-source BFSって言うっぽい？
多点BFSもmulti-source BFSもあまりメジャーな用語ではなさそうなので、使うときにはちょっと注意した方が良さそう？

多点BFSで解ける問題

数式を使って、もう少し厳密に書くと以下の通りになります。

K 個の始点 s_1,\cdots,s_K が与えられるものとし、これらの始点の集合を S とする。 このとき、各終点 t に対して \min \{ dist(i, t) \ | \ i \in S \} を求めよ。
ただし、dist(i, t) は始点 i から終点 t までの最短距離を表す。

これを通常のBFSと同じ計算量で解けるのが多点BFSです。

アルゴリズム (実装)

通常のBFSからの変更点は以下の2つだけです。

  • 最初に全ての始点をキューに追加する。
  • 全ての始点において最短距離の値（求めたい値）を0に初期化する。

発想

元のグラフに対して、新しい（ダミーの）頂点を1つ追加し、その頂点から全ての始点に対してコスト0の辺を追加することを考えます。
このとき、それぞれの始点と各終点の最短距離は、新しく追加した頂点からそれぞれの始点を通って各終点に向かう場合の最短距離と等しくなります。
よって、求めたい値は、新しく追加した頂点と各終点の最短距離に等しくなります。

なので、新しく追加した頂点から通常のBFSをすれば、求めたい値が計算できます。
このBFSをシミュレートすると、

  • キューに入っているのは始点の集合のみ
  • 全ての始点において最短距離の値が0である

という2つの条件を満たすような状態に必ずたどり着くので、結局のところ、先程のアルゴリズムで問題ないことがわかります。

問題例

  • ゾンビ島
    僕が、初めて多点BFSに出会った問題です。

  • A - Darker and Darker
    この問題が出題されたときに多点BFSの解説ツイートをしました。

発展

新しく頂点や辺を追加することで問題を解きやすくするというアイデアは、割と重要なので覚えておくと良さそうです。
参考になりそうな記事を載せておきます。

コスト0辺のテクニック - Senの競技プログラミング備忘録
区間に辺を貼る一般的なテクニック - 情報妖精の競プロ日記

おまけ（元ツイートの魚拓）

多点BFSは、始点を一つ作って、そこからコスト0の辺が多点(今回だと黒いマス)につながってるグラフを考えて、始点から普通のBFSをするっていうのを思い浮かべるとわかりやすい