密グラフに対するダイクストラ法。

「アルゴリズム・クイックリファレンス」には実験に用いたソースコードが添付されている。せっかくあるので、こちらで開発したプログラムと比較実験を行った。

用いた密グラフは TSPLIB の gr9882.tsp を変換したもので、非常に密。

graph : gr9882.tsp(TSPLIB) -> 9,882 nodes 48,822,021 arcs
Query : ss x 1
CPU   : Xeon X5460 3.16GHz

Dijkstra's algorithm with Priority Queue        12.73 sec.
Dijkstra's algorithm for Dense Graph            13.25 sec.
Optimized Dijkstra's algorithm for Dense Graph   0.51 sec.
Bellman-Ford algorithm                          43.82 sec.

msp-1.03(Dijkstra's algorithm with binary-heap)  0.30 sec.

密でもそこそこ性能出るようだ。