ダイクストラ法(Radix Heap)
(shortest-path/dijkstra-radix-heap.hpp)

• View this file on GitHub
• Last update: 2021-11-23 10:22:25+09:00
• Include: #include "shortest-path/dijkstra-radix-heap.hpp"

ダイクストラ法(Radix Heap)

ダイクストラ法の定数倍高速化ライブラリ。

概要

ダイクストラ法のヒープにRadix Heap(基数ヒープ)を使用することで最小値の取得にかかる時間計算量を高速化したライブラリ。

使い方

• dijkstra(g, start = 0): sを始点としたダイクストラ法を行い、計算結果を返す。

Depends on

• Radix Heap (data-structure/radix-heap.hpp)
• グラフテンプレート (graph/graph-template.hpp)

Verified with

• verify/verify-aoj-grl/aoj-grl-1-a-radix-heap.test.cpp
• verify/verify-unit-test/dijkstra.test.cpp

Code

#pragma once



#include "../graph/graph-template.hpp"
#include "../data-structure/radix-heap.hpp"

// unreachable -> -1
template <typename T>
vector<T> dijkstra_radix_heap(WeightedGraph<T> &g, int start = 0) {
  int N = (int)g.size();
  vector<T> d(N, T(-1));
  RadixHeap<T, int> Q;
  d[start] = 0;
  Q.push(0, start);
  while (!Q.empty()) {
    auto p = Q.pop();
    int cur = p.second;
    if (d[cur] < T(p.first)) continue;
    for (auto dst : g[cur]) {
      if (d[dst] == T(-1) || d[cur] + dst.cost < d[dst]) {
        d[dst] = d[cur] + dst.cost;
        Q.push(d[dst], dst);
      }
    }
  }
  return d;
}

/*
 * @brief ダイクストラ法(Radix Heap)
 * @docs docs/shortest-path/dijkstra-radix-heap.md
**/

#line 2 "shortest-path/dijkstra-radix-heap.hpp"



#line 2 "graph/graph-template.hpp"

template <typename T>
struct edge {
  int src, to;
  T cost;

  edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
  edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;

// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
                      bool is_1origin = true) {
  UnweightedGraph g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    if (is_1origin) x--, y--;
    g[x].push_back(y);
    if (!is_directed) g[y].push_back(x);
  }
  return g;
}

// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
                        bool is_1origin = true) {
  WeightedGraph<T> g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    cin >> c;
    if (is_1origin) x--, y--;
    g[x].emplace_back(x, y, c);
    if (!is_directed) g[y].emplace_back(y, x, c);
  }
  return g;
}

// Input of Edges
template <typename T>
Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) {
  Edges<T> es;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    es.emplace_back(x, y, c);
  }
  return es;
}

// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
                           bool is_directed = false, bool is_1origin = true) {
  vector<vector<T>> d(N, vector<T>(N, INF));
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    d[x][y] = c;
    if (!is_directed) d[y][x] = c;
  }
  return d;
}

/**
 * @brief グラフテンプレート
 * @docs docs/graph/graph-template.md
 */
#line 2 "data-structure/radix-heap.hpp"

template <typename Key, typename Val>
struct RadixHeap {
  using uint = typename make_unsigned<Key>::type;
  static constexpr int bit = sizeof(Key) * 8;
  array<vector<pair<uint, Val> >, bit + 1> vs;
  array<uint, bit + 1> ms;

  int s;
  uint last;

  RadixHeap() : s(0), last(0) { fill(begin(ms), end(ms), uint(-1)); }

  bool empty() const { return s == 0; }

  int size() const { return s; }

  __attribute__((target("lzcnt"))) inline uint64_t getbit(uint a) const {
    return 64 - _lzcnt_u64(a);
  }

  void push(const uint &key, const Val &val) {
    s++;
    uint64_t b = getbit(key ^ last);
    vs[b].emplace_back(key, val);
    ms[b] = min(key, ms[b]);
  }

  pair<uint, Val> pop() {
    if (ms[0] == uint(-1)) {
      int idx = 1;
      while (ms[idx] == uint(-1)) idx++;
      last = ms[idx];
      for (auto &p : vs[idx]) {
        uint64_t b = getbit(p.first ^ last);
        vs[b].emplace_back(p);
        ms[b] = min(p.first, ms[b]);
      }
      vs[idx].clear();
      ms[idx] = uint(-1);
    }
    --s;
    auto res = vs[0].back();
    vs[0].pop_back();
    if (vs[0].empty()) ms[0] = uint(-1);
    return res;
  }
};

/**
 * @brief Radix Heap
 * @docs docs/data-structure/radix-heap.md
 */
#line 7 "shortest-path/dijkstra-radix-heap.hpp"

// unreachable -> -1
template <typename T>
vector<T> dijkstra_radix_heap(WeightedGraph<T> &g, int start = 0) {
  int N = (int)g.size();
  vector<T> d(N, T(-1));
  RadixHeap<T, int> Q;
  d[start] = 0;
  Q.push(0, start);
  while (!Q.empty()) {
    auto p = Q.pop();
    int cur = p.second;
    if (d[cur] < T(p.first)) continue;
    for (auto dst : g[cur]) {
      if (d[dst] == T(-1) || d[cur] + dst.cost < d[dst]) {
        d[dst] = d[cur] + dst.cost;
        Q.push(d[dst], dst);
      }
    }
  }
  return d;
}

/*
 * @brief ダイクストラ法(Radix Heap)
 * @docs docs/shortest-path/dijkstra-radix-heap.md
**/

Back to top page