Dijkstra with Radix Heap
コードについての説明(個人的メモ)
Dijkstra 法を Radix Heap を用いて高速化したアルゴリズム. 辺のコストが非負"整数"の場合に用いることができる高速化である.
アルゴリズムの理解には このスライド が参考になった.
元論文は "Faster Algorithms for the Shortest Path Problem" [Ahuja, Mehlhorn, Orlin, Tarjan 1990].
時間計算量: $\O ((n + m) \log(n \cdot MAX \_ VAL))$ (辺コストの最大値を $MAX \_ VAL$ とする)
コード($n \cdot MAX \_ VAL$ が int に収まることを仮定した場合の実装)
#define impl(x, last) (x == last) ? 0 : 31 - __builtin_clz(x ^ last)
class RadixHeap{
public:
int last, size_;
vector<pair<int, int> > bucket_[32];
RadixHeap() : last(0), size_(0){}
inline pair<int, int> top(){
return pop(false);
}
inline bool empty(){
return !size_;
}
inline void push(int x, int val){
size_++, bucket_[impl(x, last)].emplace_back(x, val);
}
inline pair<int, int> pop(bool flag = true){
if(bucket_[0].empty()){
int id = 1;
while(bucket_[id].empty()) id++;
last = min_element(bucket_[id].begin(), bucket_[id].end())->first;
for(auto val : bucket_[id]){
bucket_[impl(val.first, last)].push_back(val);
}
bucket_[id].clear();
}
pair<int, int> res = bucket_[0].back();
if(flag) size_--, bucket_[0].pop_back();
return res;
}
};
class Dijkstra {
public:
struct edge{
int to, cost;
};
int V;
vector<vector<edge> > G;
vector<int> d;
using pii = pair<int, int>;
Dijkstra(int node_size) : V(node_size), G(V), d(V, numeric_limits<int>::max()){}
//無向グラフの場合
void add_edge(int u, int v, int cost){
G[u].push_back((edge){v, cost}), G[v].push_back((edge){u, cost});
}
void solve(int s){
RadixHeap que;
d[s] = 0;
que.push(0, s);
while(!que.empty()){
pii p = que.top();
que.pop();
int v = p.second;
if(d[v] < p.first) continue;
for(auto& w : G[v]){
if(d[w.to] > d[v] + w.cost){
d[w.to] = d[v] + w.cost;
que.push(d[w.to], w.to);
}
}
}
}
};