既知のエッジ重みに最適化されたプリムアルゴリズム？

Question

与えられた重みの最小値をすでに知っている場合、どのようにプリムのアルゴリズムを変更できますか？たとえば、グラフがエッジ重み0と1で構成されている場合、どのようにプリムのアルゴリズムを高速化できますか？

Answer 1

最初の戦略は、データを活用するために優先度キューを改善しているようです。ウェイトがCより小さい離散値であることが分かっている場合は、通常使用されるバイナリヒープを基数ヒープに置き換えることができます。こうすることで、フィボナッチヒープを実装するのがはるかに難しい場合と同じアルゴリズムの複雑さを簡単に得ることができます。ダイクストラ法はまったく同じデータ構造を使用し、ここでそれを基数ヒープを実装する方法の完全な説明です：

http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/spalgs/radixheap.txt

サンプルコードradixheap.cppがここで見つけることができます：

http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/spalgs/spalgs.html

プリムのアルゴリズムに同じデータ構造を適用するだけで、Dijkstraのアルゴリズムについて解説し、複雑さO（m + n log C）を得ることができます。ここで、mはエッジ、nは頂点、Cは最大エッジウェイトです。エッジウェイトが小さい整数の場合、これは実際には非常に良いことです。

基数ヒープの概念を要約すると、項目は優先順位（整数でなければならない）に従ってバケットに配置されます。バケツNによってカバーされる値の範囲は、およそ2^Nのサイズであるため、正しいバケットを見つけることは可能な最大数のログに比例します。最小の優先度を持つアイテムを抽出するとき、アイテムは時々、償却される下位のバケットに再配分され、対数的な複雑さにも作用します。

エッジウェイトが0と1の間の任意の浮動小数点数であることを意味する場合、最適化は許可されません。明らかに、すべてのエッジ重みを最大エッジ重みで除算することで、すべてのグラフを0から1の間にすることができます。この変換は、プリムのアルゴリズムをより高速に実行することはできません。結果をすべて変更せずに、すべてのエッジに同じ番号を追加するか、同じ正の数でそれらを掛けることによって、すべてのエッジを変形することができます。