bucket 法がとても改善しずらい実装(とてもシンプルであるため)であるのに対して、heap は何かと改善できる部分が多いような印象を受ける。
いま考えていることは、どちらにも適用できそうであり、実験するのが楽しみである。グラフは Forward star representation で持っているが、同一点 ID では枝長順で更にソートする。そうすれば、枝の走査時に次の候補点が見つかれば、データ構造にいれずにすぐに次の走査ができる。グラフ格納の時間が増えてしまうが。
どちらのデータ構造にも適応できると文頭で書いたが、正直 heap にしか効果がないようにも思える。bucket 法では最長枝の長さ分の配列を距離分だけインクリメントすることになってしまうからだ。また、データ構造の走査にあまり処理を要さないからだ。
いま考えていることは、どちらにも適用できそうであり、実験するのが楽しみである。グラフは Forward star representation で持っているが、同一点 ID では枝長順で更にソートする。そうすれば、枝の走査時に次の候補点が見つかれば、データ構造にいれずにすぐに次の走査ができる。グラフ格納の時間が増えてしまうが。
どちらのデータ構造にも適応できると文頭で書いたが、正直 heap にしか効果がないようにも思える。bucket 法では最長枝の長さ分の配列を距離分だけインクリメントすることになってしまうからだ。また、データ構造の走査にあまり処理を要さないからだ。