1コアなら最速マシンであろう Intel(R) Core(TM) i7 CPU 965 @ 3.20GHz で比較実験を行った。SSSP の実行時間が4秒を切る。
○ 最短路ソルバ
mbp: Dijkstra's algorithm with multi-level buckets (by A.V.Goldberg)
msp-1.13: Dijkstra's algorithm with binary-heap (by Y.Yasui)
○ クエリ
全米道路ネットワーク(USA-road-d.USA.gr)上での1対全最短路問題(SSSP)
○ SSSP1クエリあたりの実行時間(SSSP/query)[スレッド数]
mbp : 4.27 sec.
msp-1.13[1] 3.97 sec.
msp-1.13[2] 2.05 sec.
msp-1.13[4] 1.16 sec.
msp-1.13[1](LargePage) 3.97 sec.
msp-1.13[2](LargePage) 2.00 sec.
msp-1.13[4](LargePage) 1.12 sec.
○ 最短路ソルバ
mbp: Dijkstra's algorithm with multi-level buckets (by A.V.Goldberg)
msp-1.13: Dijkstra's algorithm with binary-heap (by Y.Yasui)
○ クエリ
全米道路ネットワーク(USA-road-d.USA.gr)上での1対全最短路問題(SSSP)
○ SSSP1クエリあたりの実行時間(SSSP/query)[スレッド数]
mbp : 4.27 sec.
msp-1.13[1] 3.97 sec.
msp-1.13[2] 2.05 sec.
msp-1.13[4] 1.16 sec.
msp-1.13[1](LargePage) 3.97 sec.
msp-1.13[2](LargePage) 2.00 sec.
msp-1.13[4](LargePage) 1.12 sec.