最短路とデータ構造。

前回、ポテンシャルの更新の部分を見直したので、今度はデータ構造への入出力の動きをしっかり見ていこう。

以前データ構造は２分木を用いていた。２分木は扱うデータの特性を気にすることなく扱えるが、最短路で扱うデータにはある程度の幅があり、また取り出したい値というのは少しずつ大きくなっていくという性質がある。せっかくそのような性質があるのに考慮しないのはもったいないので、最近はバケット法（バケット用の配列のほかに prev, next のポインタをもっている）を用いている。

また、探索点になる点のポテンシャルの動きを観察してみたが、１回１回の差が非常に小さい。一番大きな場所が最初の１回目ということもあった。全米データを例にあげると枝は最短 1 最長 368855 であるのだが、この幅以上に点数 (23,947,347) や枝数 (58,333,344) が多いために差が小さくなっている(最大でも 20,000 程度であるがとてもまれであり、ほとんどが数十以下)のであろうか。このくらいであればもしかしたら、prev, next をなくしてみても良いのかもしれない。いろいろ試してみよう。