全米道路ネットワークに対する 全対全最短路問題

全米道路ネットワーク(点数 23,947,347, 枝数 58,333,344)に対して全対全最短路を計算することを行った。単に１対全最短路を複数回（点数の数）計算を行うのは、様々な意味でコストが大き過ぎるので、いろいろな工夫を試している。以下の結果では AMD Magny-Cours 48 コアのマシンを用いて全対全最短路の計算を行っているが、計算時間を 7.75日に減少させることに成功した。もし仮に百万コアを計算に利用できると仮定すると 30 秒ほどで計算が終了することになる。