アカウント名:
パスワード:
DijkstraをC++で書くのだったら、priority_queueを使えば早いんじゃないかなーとか思ったり。heapと一緒ですよね。
私も最初はそれを考えたんですけど、Dijkstra法だと「最小キーの要素をヒープから取り除く」とか、「キーの値を減少させる」とかいう操作が入ってきますよね？手持ちの資料 (プログラミング言語C++, ASCII) だとそういった手続きをO(log n)（nはヒープの要素数）くらいの実行時間になるようにpriority_queueで実装されている（か、実装できる）かどうか見当がつかなかったので、手元の資料(Introduction to Algorithms, MIT press)にある「二項ヒープ」を実装してみたわけです。疑似コードをC++に落とすだけでしたので、あんまり考える必要がありませんでした。# 結局デバグに時間を取られましたけど（汗
なお、実装は大変ですが、最速を目指すなら二項ヒープでなくてフィボナッチヒープを実装するのがいいようですね。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
あつくて寝られない時はhackしろ! 386BSD(98)はそうやってつくられましたよ? -- あるハッカー
priority_queue (スコア:1)
DijkstraをC++で書くのだったら、priority_queueを使えば早いんじゃないかなーとか思ったり。
heapと一緒ですよね。
Re:priority_queue (スコア:1)
私も最初はそれを考えたんですけど、Dijkstra法だと「最小キーの要素をヒープから取り除く」とか、「キーの値を減少させる」とかいう操作が入ってきますよね？
手持ちの資料 (プログラミング言語C++, ASCII) だとそういった手続きをO(log n)（nはヒープの要素数）くらいの実行時間になるようにpriority_queueで実装されている（か、実装できる）かどうか見当がつかなかったので、手元の資料(Introduction to Algorithms, MIT press)にある「二項ヒープ」を実装してみたわけです。疑似コードをC++に落とすだけでしたので、あんまり考える必要がありませんでした。
# 結局デバグに時間を取られましたけど（汗
なお、実装は大変ですが、最速を目指すなら二項ヒープでなくてフィボナッチヒープを実装するのがいいようですね。