第5回 SCOPE。

どちらのお話も興味深く聞かせていただきました。船の最短路に登場してきたグラフの規模は確か 3万点 70万枝ほどの規模だったと思うので、近いグラフを選択して解いてみた。

使用したソルバは、Goldberg 氏の splib.tar に入っているもの。

●グラフ
USA-road-d.NY.gr
Nodes: 264346    Arcs: 733846

●1対全最短路問題の実行時間(Xeon X5460 3.16GHz / gcc-4.1.2)
[1] Bellman-Ford             : 1.63 sec.
[2] Dijkstra                 : 0.57 sec.
[3] Dijkstra with 4-ary heap : 0.05 sec.