全点間最短経路の計算をちょっとの工夫でちょっと速くする話

概要

最近研究で重みなし連結正則グラフの全点間の最短経路を求めることが多く、ちょっと工夫したらちょっとだけ早くなったのでそれについて簡単に書きます。

素朴な方法

一番素朴な方法としては幅優先探索があります。
全ての頂点から幅優先探索をして全点間の最短経路を全て計算する方法です。

アルゴリズム

ところである点から幅優先探索を行うと図のように三角形みたいな図が出てくると思います。



　　　　　　　　　　　　　　

　幅優先探索をやっているとキューに頂点を取り出しては突っ込んでを繰り返して最短距離を計算していくわけですが、よく考えるとこの図の最下層にいる頂点たちはキューから取り出されてもその後何もせずに放り投げられてしまうことになります。したがって、キューに突っ込んだ頂点の個数がグラフの頂点数とちょうど等しくなったらキューを空にして幅優先を終了し、別の頂点からまた幅優先する」というアルゴリズムでちょっとだけ計算が速くなることが期待されます。
　考え方としては簡単でセコイように見えますが、グラフの形状によっては紫の部分の頂点がすごく多かったりすることがあるので、密なグラフに対してはそこそこ高速になるんじゃないかと期待できることと思われます。

数値実験

ということで幾つかの種類のグラフに対し「全点間最短経路長」を計算する以下に示す２つのプログラムを用意し、比較しました。
A. 素朴な幅優先探索
B. 上に述べた工夫をしたもの

用意したグラフは次のモデルによって生成されたグラフです。
1. Erdős–Rényi model (最も代表的なランダムグラフのモデル)
2. Configuration Model (ランダム正則グラフの代表的なモデル)

　　　　　　　　　　　

Erdős–Rényi modelによって生成されたグラフに対するプログラムの実行時間の比較です。
横軸はモデルのパラメータpの値で、右に行くほど辺の本数が多くなっています。頂点数は10000で固定しています。 縦軸は実行時間で、単位は[ms]です。紫の線が素朴な方法(A)で、緑の線が工夫したもの(B)です。


Configuration Modelによって生成されたグラフでの比較です。横軸は頂点の次数を表しているため、右に行くほど線形で辺の本数が増えていきます。縦軸は先ほどと同様に実行時間で単位は[ms]です。頂点数は10000です。なお、１番目の実験で生成したグラフよりも辺数は圧倒的に少ないためこちらの方が実行時間はかなり短くなっています。紫が素朴な方法で、緑が工夫した方法です。


二つの結果を見ると、意外とこの工夫によって早くなることが分かると思います。

考察・まとめ

・ 空間計算量を変えずにちょっとした工夫でBFSを早くするという話でした。

・ 恐らく緑の方では実行時間はグラフの直径によって大きく左右されるのでほぼ横ばいみたいな感じになっていると思います。
・ 直径をDだとすると、#{ 最短距離がDとなるような頂点ペア } が多いほど工夫が効果的になると思います。
・ したがって例えばグラフが木だったりするとぜんぜん効果がないと思います。

・ 実データとかでは実験してないのでその辺を含めてもうちょっと調べてみたいと思います。
・ さすがにこれくらいの工夫は誰か思いついてるでしょ...