c++ - c++ std::priority_queue はダイクストラ キューの正しい構造ですか

Question

C++ プライオリティ キューはダイクストラ キューに適した構造ではないと思います。要素を簡単に検索または削除するための機能が含まれていないからです。

正しい構造はフィボナッチ ヒープですが、std ライブラリにはありません。

より優れた C++ 実装の構造について提案がある人はいますか?

Answer 1

std::setペア <distance, vertex> を使用して保存できます。要素を検索して削除するには、配列内またはstd::vector特定の頂点のペア<距離、頂点> をすばやく取得するために、各頂点までの距離を保つことができます。最も近い未訪問の頂点は、常にセットの最初の要素にあります (および を使用して取得できますset.begin())。

Answer 2

ほとんどの実用的な目的では、std::priority_queueベースの実装はスパース グラフには十分です。この方法で Dijkstra を実装すると、実行時間がO(E log V). 十分に密度の高いグラフがある場合は、単純O(V*V)にダイクストラのアルゴリズムの基本バージョンを使用できます。グラフが密になるにつれて、Fib ヒープ バージョンの漸近線はバニラの実装に近づきます。