dijkstra_priority_queue
クラス · 単一始点最短路 (shortest_path)
template <class Key, class Value, class Comp = std::less<>>
struct dijkstra_priority_queue;
概要
shortest_path の既定ヒープ（std::priority_queue ベースの最小ヒープ）
順序基準 Key（距離）・付随データ Value（頂点）を受け取り、Key 最小を ルートにする。binary_heap / fibonacci_heap と同じ template-template 形式 （Heap<Key, Value, Comp>）で渡せるよう薄く包む。decrease-key は持たない。
計算量
- 各更新は $O(\log n)$、
emptyとtopは $O(1)$
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
empty |
空か返す | $O(1)$ |
push |
keyとvalueを追加する | $O(\log n)$ |
top |
最小keyの要素を返す | $O(1)$ |
pop |
最小keyの要素を削除する | $O(\log n)$ |
メンバ型
| 名前 | 説明 | 計算量 |
|---|---|---|
node |
ヒープに格納する順序基準と付随データの組 | 型エイリアスで実行時計算量はない |
メンバ変数
| 名前 | 説明 | 計算量 |
|---|---|---|
que |
要素を保持する優先度付きキュー | top は $O(1)$、更新は $O(\log n)$ |
関連項目
decrease_key_heap— decrease-key（update）を持つヒープかshortest_path— 単一始点最短路（実重み付きグラフはダイクストラ法）shortest_path_negative— 単一始点最短路（負辺ありはベルマンフォード法）shortest_path_spfa— 単一始点最短路（負辺ありは SPFA）