cp-library

競技プログラミング用 C++ ライブラリ

View the Project on GitHub qandori/cp-library

:heavy_check_mark: Dijkstra の内部キュー

components/dijkstra_queue.hpp · GitHub で見る

共通ページ

shortest_path_detail::RadixQueue<T> は Dijkstra が使う単調優先度キューです。通常は dijkstra・dijkstra_path を使います。T は 64 bit 以下の整数型、キーは非負です。頂点番号は非負の int です。

shortest_path_detail::DistanceQueue<T> は、通常の Dijkstra とトポロジカル前処理で共有するキュー型です。64 bit 以下の整数距離には RadixQueue<T>、それ以外には二分ヒープの BinaryQueue<T> を使います。いずれも empty()・push(key,vertex)・pop() を持ち、pop() は最小キーと頂点の pair<T,int> を返します。要素数を \(q\) として、二分ヒープの追加・削除は \(O(\log q)\) 時間、空間は \(O(q)\) です。

操作 内容・返り値 計算量
RadixQueue<T>() 下限 0 の空キューを作る \(O(w)\)
empty() 要素がないか \(O(1)\)
push(key,vertex) 最後に取り出したキー以上の要素を追加 償却 \(O(1)\)
pop() 最小キーと頂点の pair<T,int> を返して削除。非空が必要 償却 \(O(w)\)

要素が 32 個以下の間は、小さい固定配列から最小値を選びます。33 個以上になった後は radix heap を使います。全ての未処理キーが現在の下限から \(2^{31}-1\) 以内なら、キーの下位 32 bit と頂点番号を 64 bit にまとめます。距離そのものは元の型で保持し、32 bit の境界を何度越えても扱えます。条件を満たさない追加があれば、未処理キーを復元して 64 bit の radix heap に移します。

バケットの最小キーを追加時に保存し、非空のバケットを bit 列で管理します。Dijkstra 法の最小距離を確定する順序は変えません。CPU 固有の命令を直接使わず、GCC・Clang・Mac で動作します。

次のバケットに要素が 1 個だけある場合は、その要素を直接返して再配置を省きます。

キーの bit 数を \(w\le64\)、同時に保持する要素数の最大を \(q\) として、追加は償却 \(O(1)\)、取り出しは償却 \(O(w)\)、空間は \(O(q+w)\) です。64 bit へ移行する 1 回だけは、その時点の要素数に比例する処理が加わります。

依存ライブラリ

検証コード

コード

#ifndef DIJKSTRA_QUEUE_HPP
#define DIJKSTRA_QUEUE_HPP

#include "RadixHeap.hpp"
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>

namespace shortest_path_detail {
template<class Weight, class Distance>
bool reaches_limit(const Weight &weight, const Distance &limit) {
	if constexpr (std::numeric_limits<Weight>::is_integer && std::numeric_limits<Weight>::is_bounded &&
				  std::numeric_limits<Distance>::is_integer && std::numeric_limits<Distance>::is_bounded) {
		using Compare = std::common_type_t<Weight, Distance>;
		return Compare(weight) >= Compare(limit);
	} else return weight >= limit;
}

template<class T> class RadixQueue {
	static_assert(std::is_integral_v<T> && sizeof(T) <= 8);
	struct State { T key; int vertex; };
	State small_[32];
	std::vector<std::uint64_t> buckets_[33];
	std::uint32_t minimum_[33];
	std::uint32_t occupied_ = 0;
	std::uint64_t last_ = 0;
	std::size_t count_ = 0;
	int mode_ = 0;
	RadixHeap<std::uint64_t> wide_;
	void put(std::uint64_t state) {
		std::uint32_t key = state >> 32;
		int index = std::bit_width(key ^ std::uint32_t(last_));
		buckets_[index].push_back(state);
		if (index) {
			occupied_ |= std::uint32_t(1) << (index - 1);
			minimum_[index] = std::min(minimum_[index], key);
		}
	}
	void promote() {
		if (mode_ == 0) {
			for (std::size_t i = 0; i < count_; ++i) wide_.push({std::uint64_t(small_[i].key), small_[i].vertex});
		} else {
			for (auto &bucket : buckets_) {
				for (auto state : bucket) {
					std::uint64_t key = last_ + std::uint32_t(std::uint32_t(state >> 32) - std::uint32_t(last_));
					wide_.push({key, int(std::uint32_t(state))});
				}
				bucket.clear();
			}
		}
		mode_ = 2;
	}

  public:
	bool empty() const { return count_ == 0; }
	void push(T key, int vertex) {
		assert(key >= 0 && std::uint64_t(key) >= last_);
		if (mode_ == 0 && count_ < 32) {
			small_[count_++] = {key, vertex};
			return;
		}
		if (mode_ == 0) {
			bool narrow = std::uint64_t(key) - last_ <= std::uint64_t(std::numeric_limits<std::int32_t>::max());
			for (std::size_t i = 0; i < count_; ++i)
				narrow &= std::uint64_t(small_[i].key) - last_ <= std::uint64_t(std::numeric_limits<std::int32_t>::max());
			if (narrow) {
				std::fill_n(minimum_, 33, std::numeric_limits<std::uint32_t>::max());
				for (std::size_t i = 0; i < count_; ++i)
					put((std::uint64_t(std::uint32_t(small_[i].key)) << 32) | std::uint32_t(small_[i].vertex));
				mode_ = 1;
			} else promote();
		}
		if (mode_ == 1 && std::uint64_t(key) - last_ > std::uint64_t(std::numeric_limits<std::int32_t>::max())) promote();
		if (mode_ == 2) wide_.push({std::uint64_t(key), vertex});
		else put((std::uint64_t(std::uint32_t(key)) << 32) | std::uint32_t(vertex));
		++count_;
	}
	std::pair<T, int> pop() {
		assert(count_);
		if (mode_ == 0) {
			std::size_t best = 0;
			for (std::size_t i = 1; i < count_; ++i)
				if (small_[i].key < small_[best].key) best = i;
			State state = small_[best];
			small_[best] = small_[--count_];
			last_ = std::uint64_t(state.key);
			return {state.key, state.vertex};
		}
		if (mode_ == 2) {
			auto state = wide_.pop_value();
			last_ = state.first;
			--count_;
			return {T(state.first), state.second};
		}
		if (buckets_[0].empty()) {
			int index = std::countr_zero(occupied_) + 1;
			last_ += std::uint32_t(minimum_[index] - std::uint32_t(last_));
			minimum_[index] = std::numeric_limits<std::uint32_t>::max();
			occupied_ &= occupied_ - 1;
			if (buckets_[index].size() == 1) {
				auto state = buckets_[index].back();
				buckets_[index].clear();
				--count_;
				return {T(last_), int(std::uint32_t(state))};
			}
			for (auto state : buckets_[index]) put(state);
			buckets_[index].clear();
		}
		auto state = buckets_[0].back();
		buckets_[0].pop_back();
		--count_;
		return {T(last_), int(std::uint32_t(state))};
	}
};

template<class T> class BinaryQueue {
	using State = std::pair<T, int>;
	std::vector<State> heap_;

  public:
	bool empty() const { return heap_.empty(); }
	void push(T cost, int vertex) {
		heap_.emplace_back(std::move(cost), vertex);
		std::push_heap(heap_.begin(), heap_.end(), std::greater<State>());
	}
	State pop() {
		std::pop_heap(heap_.begin(), heap_.end(), std::greater<State>());
		State state = std::move(heap_.back());
		heap_.pop_back();
		return state;
	}
};

template<class T>
using DistanceQueue = std::conditional_t<std::is_integral_v<T> && sizeof(T) <= 8, RadixQueue<T>, BinaryQueue<T>>;
}

#endif
Back to top page