全対全最短路問題。

HPCS2010(二日目のみ) へ参加。残念ながら発表自体は聞けなかったのだが、「GPU上での高速なブロック化フロイド・ワーシャル法」という発表があったようだ。nVIDIA GeForce GTX 280 上で n = 8192 のときの実行時間は 4940 msec だそうだ。

フロイド・ワーシャル法(Warshall-Floyd Algorithm)は、重み付き有向グラフに対する全対全最短経路問題を多項式時間(Θ(n^3))に計算可能。基本的に３重ループで、グラフの特性に実行時間は依存しにくい。

全米データ(2400万点, 5800万枝)のような非常に大きなグラフを使用する場合、フロイド・ワーシャル法ではメモリ要求量が大きすぎて実行不可能になってしまうので、ダイクストラ法(Dijkstra's algorithm)を用いることになる。ダイクストラ法で全対全を解く場合、各点を始点として１対全最短路問題を計算すればよい。

ダイクストラ法は枝数やグラフ・トポロジーにも実行時間が依存するため、単純に比べることは難しいが、疎グラフであれば非常に高速に解ける。

CPU    : Intel(R) Xeon(R) CPU X5550 @ 2.67GHz (4cores x 2sockets)
GCC    : 4.4.2
OS     : linux 2.6.31.12-174.2.3.fc12.x86_64

solver : Dijkstra's algorithm & binary-heap (8threads)
graph  : 8100 nodes 24210 arcs
memory : 1.70 MB
time   : 0.500 sec.