!先日参加したコンテストで以下のような問題が出題されました1。シンプルなグラフがある。それぞれの頂点は最大で100個ほどのグループに分けられている。各頂点から各グループの頂点までの最短距離を求めよ。頂点の最大数は\(10^{5}\)である。この問題、コンテスト中には全く手が出ませんでした。それぞれの頂点から幅優先探索を行なって任意のグループに属する頂点に出会う度に記録すれば、目的はまあ達成です。計算量は軽く見積もっても\(O(N^{2})\)。\(10^{10}\)を超えてしまいます。100\)のテーブルを用意して記録していけばよいように思うのですが、うまく埋めていくことができませんでした。このときは次のように考えていました。各頂点から幅優先探索を行う。訪れた頂点のグループ情報を得る。そのグループに初めて訪れているなら、距離を最短距離として記録する(全てのグループに出会ったらその頂点に関しての探索は終了する)さてコンテスト終了後に色々考えても計算量が落とせなかったので他のコンテスタントの実装を読んでみました。皆幅優先探索を実装しているようですが、探索をグループの数分しか行なっていません...はて?ポイントは以下でした。幅優先探索の開始点はグループに属する全頂点とする(!)幅優先探索を行う。とでも呼称できそうな技法です。以下のような盤面を考えてみます。ここで、グループは4色の色として表しています。以下のように探索を行います。この緑色の頂点はすぐに、青色と紫色の点を見つけることができますが、赤色の頂点にたどり着くまでには3ステップかかっていることが分かります。赤色の頂点にたどり着いた時点で自分が属する色以外の3色の頂点にたどり着いたのでここで探索を打ち切ることはできますが、最悪\(O(N)\)の探索を\(N\)回繰り返さなければならないので、計算量は依然\(O(N^{2})\)と考えたほうがよいでしょう。多点開始幅探索を見て見ましょう。探索は以下のようになされているようです。先ほどの単開始点から行う幅優先探索に比べて、ほとんどの頂点をすぐ網羅することも注目しましょう。一回の探索で訪れる頂点の数は単点開始でも多点開始でも\(N\)ですが、探索を全体で\(N\)回(最大\(10^{5}\)回)やらなければいけないか、\(M\)回(最大100回)でいいのかで総合的な計算量は大きく変わります。覚えておきたい技法です。Programming(1...昨年のSIGGRAPH参加後、9月ほどからでしょうか。