最短路。

以前作成した Dijsktra 法で最短路を解くプログラムを見返してみた。
その当時、できるだけのことはしたつもりだったが、今更になってよくない部分がたくさん見つかった。
以前はそういった部分を発見する力がなかったのだろうか。

結局、気になってほぼすべてのソースを見直すことになってしまったが、
その甲斐もあり、54.5 秒程かかっていた実行時間を 45.5 秒 程に落とすことが出来た。

まだブロッキング等の最適化手法を用いていないので、まだまだ高速化できそうだ。


[xxxxx@xxxx src]$ ./shortestpath p2p s ../../../data/USA/USA-road-t.USA.grap ../../../data/USA/query_USA.p2p
shortest path route start at Mon Nov 5 17:27:31 2007
algorithm is dijkstra method
mode is p2p & sorted dimacs graph
data (.gr) is ../../../data/USA/USA-road-t.USA.grap
query (.ss) is ../../../data/USA/query_USA.p2p
node number is 23947347
arc number is 58333344

[ 1/10] 957498-10453327
Distance = 41922812, ScanNode = 20358763, CalcTime : 7155.9[ms]

[ 2/10] 19200797-7727679
Distance = 8047405, ScanNode = 4429158, CalcTime : 1629.8[ms]

[ 3/10] 13006257-40639
Distance = 18835334, ScanNode = 13443219, CalcTime : 6105.1[ms]

[ 4/10] 4314559-22779984
Distance = 36904098, ScanNode = 13290596, CalcTime : 4628.3[ms]

[ 5/10] 17261435-8424294
Distance = 4202750, ScanNode = 971469, CalcTime : 371.9[ms]

[ 6/10] 8077810-13186938
Distance = 35317539, ScanNode = 19042418, CalcTime : 6776.0[ms]

[ 7/10] 3048748-1475829
Distance = 16883055, ScanNode = 8263299, CalcTime : 2973.5[ms]

[ 8/10] 21869636-3531883
Distance = 21836097, ScanNode = 4511822, CalcTime : 1393.8[ms]

[ 9/10] 13446936-4981527
Distance = 42431566, ScanNode = 20211716, CalcTime : 7601.8[ms]

[10/10] 18549540-3230879
Distance = 22838781, ScanNode = 16118473, CalcTime : 6877.0[ms]

File Read Time : 23819.4[ms]
Total Calc Time : 45513.1[ms]