ダイクストラ法: 初期化

Dijkstra法では実行前に、始点からの距離 d(v), 直前点 p(v) といったラベルを初期化する必要があるが始点終点間が短い場合この初期化がバカにならない。

そこで time stamp を導入し、初期化が必要であるときまで初期化を
実際 Goldberg の mbp でもそのように実装されている。

簡単ではあるがサンプルプログラムを作成し実験してみた。

1. 近い点の場合

※ 画像は両方向だが、実験には通常の Dijkstra with 2-heap

normal 0.556s
time stamp 0.769s

2. 遠い点の場合

※ 画像は両方向だが、実験には通常の Dijkstra with 2-heap

normal 4.314s
time stamp 4.928s

3. まとめ
結果としてあれ？といったところ。