最短路に用いるデータ構造。

ダイクストラ法はとても効率的に最短路を求めることができるアルゴリズムであるが、
走査した際に求めたポテンシャルをどのように格納するかでかなり差が出ることが分かった。


■現時点では「BinaryTree」か「BinaryHeap」で格納している。
○BinaryTree
　こちらは BinaryTree へ値を挿入・削除するたびに、malloc/free している。
　BinaryTree にデータがある場合とない場合で場合分けをしている。
　　ある→それを削除し、更新したものを改めて挿入する
　　ない→挿入する

○BinaryHeap
　一度に配列で確保しているので、この部分に関しては「BinaryTree」よりは効率である。
　頂いたプログラムをそのまま加えただけなので、場合分けはしていない。



■用いたデータ
Distance graph :
DIMACS Full USA (23947347 nodes and 58333344 arcs)

Query :
10
957498 10453327
19200797 7727679
13006257 40639
4314559 22779984
17261435 8424294
8077810 13186938
3048748 1475829
21869636 3531883
13446936 4981527
18549540 3230879


○Pentium M 1.60GHz / 896MB
　FileReadTime　　　　　　　　　８１秒
　Dijkstra With BinaryTree　　１０６秒
　Dijkstra With BinaryHeap　　１３２秒


○Xeon 3.0GHz x 2 / 8GB
　FileReadTime　　　　　　　　　２３秒
　Dijkstra With BinaryTree　　　４５秒
　Dijkstra With BinaryHeap　　　５７秒


このように現時点では「BinaryTree」の方が高速なのだが、
場合分けを採用すれば「BinaryHeap」にもまだまだ分があるだろう。

ポインタは遅いと言われてきたがここまで差があるのであれば、
やはり「Fibonacci Heap」が有効なのかもしれない。
とりあえず授業（Ｒやらプレゼン）が一段落したので、作ってみよう。