decrease_key_heap

コンセプト · 単一始点最短路 (shortest_path)

template <class Heap, class Key, class Value>
concept decrease_key_heap = requires(Heap &h, Key key, Value value) {
    requires requires(decltype(h.push(key, value)) handle) { h.update(handle, key); };
};

概要

decrease-key（update）を持つヒープか

binary_heap / fibonacci_heap は満たし、dijkstra_priority_queue は満たさない。

計算量

• コンパイル時制約で実行時計算量はない

関連項目

• dijkstra_priority_queue — shortest_path の既定ヒープ（std::priority_queue ベースの最小ヒープ）
• shortest_path — 単一始点最短路（実重み付きグラフはダイクストラ法）
• shortest_path_negative — 単一始点最短路（負辺ありはベルマンフォード法）
• shortest_path_spfa — 単一始点最短路（負辺ありは SPFA）