Heap

ここ数日, Dijkstra法が速くならないかと思ってFibonacci Heapを勉強して実装してみたんだけど, Binary Heapに較べて全く速くならなかった. なんだかなあ. もっともっと問題のサイズを大きくしたら違うのかもしれないけど, この場合どうもメモリ使用量の限界にひっかかってしまうみたいだ.

速度の比較は10^5頂点10^7辺くらいまでのグラフで行った. Fibonacci Heapは期待はずれだったから, あとは状況に適した工夫をして頑張るみたいな感じなんだろうか. まあ実装に問題があるのかもしれない.

なんだか時間を無駄にした気もするけど, 勉強になったからいいかなあ. ちなみにFibonacci Heapを実装する際に参考にしたのはamazon:Introduction to Algorithmsで紹介されているもの.