読者です 読者をやめる 読者になる 読者になる

Dijkstra's Algorithm

最近 Dijkstra's Algorithm の話があったので, ちょっと思い出したことを徒然と.
この algorithm では, 次に始点から一番近い頂点を探すときに heap を使うことが多いかと思います. しかし, priority_queue とか PriorityQueue には, すでに heap に入っている頂点までの距離を更新するための操作 decreaseKey が欠けています. *1 これに対する妥協案でよくあるのをまとめると次の2つになったような気がします.

更新しない

古い距離を key にした頂点を heap から取り除かずに, 新しい距離を key にした頂点を新たに heap に突っ込むというもの. よく最後に通った辺を突っ込むとも言われます. もちろん, この方法だとゴミがいっぱい入ってしまうので, 取り出したときに最小値にならない key が付いているものを捨てる必要があります.
これでも, order は悪くならないけれども, やはり heap size がどうしても大きくなってしまう場合があるので, memory が気になるときにはちょっと困るかもしれません.

平衡2分探索木を使う

set とか TreeSet とかを使うと赤黒木なので, 削除して, 更新して, 入れなおすとかすると O(log n) で decreaseKey が実現できます. これだと無駄な要素が入らないので, いい感じになります. wakaba で Java で実験したときにはおおよそこっちのほうがよかったです.
ただ, 注意しないといけないのは set なので, 同じ距離の頂点間にも順序がついていないといけないということです. ここは要注意です.

おまけ

他にもありましたら教えてくださると嬉しいです.
あと, binary heap って 平衡2分探索木よりできることが少ないのに計算量が減っていなくてダメな子ですよね...

*1:むしろ実装を考えるとなくて当たり前ですが.