ダイクストラ法(定数倍高速化)
(shortest-path/dijkstra-fast.hpp)

• View this file on GitHub
• Last update: 2020-12-17 01:20:11+09:00
• Include: #include "shortest-path/dijkstra-fast.hpp"

定数倍高速化ダイクストラ法

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

概要

ダイクストラ法を空間・時間ともに定数倍高速化したライブラリ。

ナイーブな実装と雑なランダムケースで比較したところ、全体としておよそ2倍程度の高速化がなされるようだ。

使い方

• dijkstra(g, s): sを始点としたダイクストラ法を行い、計算結果を返す。
• dijkstra_restore(g, s): sを始点としたダイクストラ法(復元付き)を行い、計算結果を返す。
  • いずれの場合もgはStaticGraphである必要がある。

Depends on

• Radix Heap (data-structure/radix-heap.hpp)
• Static Graph (graph/static-graph.hpp)

Verified with

• verify/verify-aoj-grl/aoj-grl-1-a-fast-dijkstra.test.cpp
• verify/verify-unit-test/dijkstra.test.cpp
• verify/verify-yosupo-graph/yosupo-shortest-path-3.test.cpp
• verify/verify-yuki/yuki-1320.test.cpp

Code

#pragma once

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

template <typename T>
vector<T> dijkstra(StaticGraph<T>& g, int start = 0) {
  vector<T> d(g.size(), T(-1));
  RadixHeap<T, int> Q;
  d[start] = 0;
  Q.push(0, start);
  while (!Q.empty()) {
    auto p = Q.pop();
    int u = p.second;
    if (d[u] < T(p.first)) continue;
    T du = d[u];
    for (auto&& [v, c] : g[u]) {
      if (d[v] == T(-1) || du + c < d[v]) {
        d[v] = du + c;
        Q.push(d[v], v);
      }
    }
  }
  return d;
}

template <typename T>
T dijkstra_point(StaticGraph<T>& g, int start, int goal) {
  vector<T> d(g.size(), T(-1));
  RadixHeap<T, int> Q;
  d[start] = 0;
  Q.push(0, start);
  while (!Q.empty()) {
    auto p = Q.pop();
    int u = p.second;
    if(u == goal) return d[u];
    if (d[u] < T(p.first)) continue;
    T du = d[u];
    for (auto&& [v, c] : g[u]) {
      if (d[v] == T(-1) || du + c < d[v]) {
        d[v] = du + c;
        Q.push(d[v], v);
      }
    }
  }
  return -1;
}

template <typename T>
vector<pair<T, int>> dijkstra_restore(StaticGraph<T>& g, int start = 0) {
  vector<pair<T, int>> d(g.size(), {T(-1), -1});
  RadixHeap<T, int> Q;
  d[start] = {0, -1};
  Q.push(0, start);
  while (!Q.empty()) {
    auto p = Q.pop();
    int u = p.second;
    if (d[u].first < T(p.first)) continue;
    T du = d[u].first;
    for (auto&& [v, c] : g[u]) {
      if (d[v].first == T(-1) || du + c < d[v].first) {
        d[v] = {du + c, u};
        Q.push(du + c, v);
      }
    }
  }
  return d;
}

/*
 * @brief ダイクストラ法(定数倍高速化)
 * @docs docs/shortest-path/dijkstra-fast.md
 **/

#line 2 "shortest-path/dijkstra-fast.hpp"

#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 2 "graph/static-graph.hpp"

namespace StaticGraphImpl {

template <typename T, bool Cond = is_void<T>::value>
struct E;
template <typename T>
struct E<T, false> {
  int to;
  T cost;
  E() {}
  E(const int& v, const T& c) : to(v), cost(c) {}
  operator int() const { return to; }
};
template <typename T>
struct E<T, true> {
  int to;
  E() {}
  E(const int& v) : to(v) {}
  operator int() const { return to; }
};

template <typename T = void>
struct StaticGraph {
 private:
  template <typename It>
  struct Es {
    It b, e;
    It begin() const { return b; }
    It end() const { return e; }
    int size() const { return int(e - b); }
    auto&& operator[](int i) const { return b[i]; }
  };
  
  int N, M, ec;
  vector<int> head;
  vector<pair<int, E<T>>> buf;
  vector<E<T>> es;

  void build() {
    partial_sum(begin(head), end(head), begin(head));
    es.resize(M);
    for (auto&& [u, e] : buf) es[--head[u]] = e;
  }

 public:
  StaticGraph(int _n, int _m) : N(_n), M(_m), ec(0), head(N + 1, 0) {
    buf.reserve(M);
  }

  template <typename... Args>
  void add_edge(int u, Args&&... args) {
#pragma GCC diagnostic ignored "-Wnarrowing"
    buf.emplace_back(u, E<T>{std::forward<Args>(args)...});
#pragma GCC diagnostic warning "-Wnarrowing"
    ++head[u];
    if ((int)buf.size() == M) build();
  }

  Es<typename vector<E<T>>::iterator> operator[](int u) {
    return {begin(es) + head[u], begin(es) + head[u + 1]};
  }
  const Es<typename vector<E<T>>::const_iterator> operator[](int u) const {
    return {begin(es) + head[u], begin(es) + head[u + 1]};
  }
  int size() const { return N; }
};

}  // namespace StaticGraphImpl

using StaticGraphImpl::StaticGraph;

/**
 * @brief Static Graph
 * @docs docs/graph/static-graph.md
 */
#line 5 "shortest-path/dijkstra-fast.hpp"

template <typename T>
vector<T> dijkstra(StaticGraph<T>& g, int start = 0) {
  vector<T> d(g.size(), T(-1));
  RadixHeap<T, int> Q;
  d[start] = 0;
  Q.push(0, start);
  while (!Q.empty()) {
    auto p = Q.pop();
    int u = p.second;
    if (d[u] < T(p.first)) continue;
    T du = d[u];
    for (auto&& [v, c] : g[u]) {
      if (d[v] == T(-1) || du + c < d[v]) {
        d[v] = du + c;
        Q.push(d[v], v);
      }
    }
  }
  return d;
}

template <typename T>
T dijkstra_point(StaticGraph<T>& g, int start, int goal) {
  vector<T> d(g.size(), T(-1));
  RadixHeap<T, int> Q;
  d[start] = 0;
  Q.push(0, start);
  while (!Q.empty()) {
    auto p = Q.pop();
    int u = p.second;
    if(u == goal) return d[u];
    if (d[u] < T(p.first)) continue;
    T du = d[u];
    for (auto&& [v, c] : g[u]) {
      if (d[v] == T(-1) || du + c < d[v]) {
        d[v] = du + c;
        Q.push(d[v], v);
      }
    }
  }
  return -1;
}

template <typename T>
vector<pair<T, int>> dijkstra_restore(StaticGraph<T>& g, int start = 0) {
  vector<pair<T, int>> d(g.size(), {T(-1), -1});
  RadixHeap<T, int> Q;
  d[start] = {0, -1};
  Q.push(0, start);
  while (!Q.empty()) {
    auto p = Q.pop();
    int u = p.second;
    if (d[u].first < T(p.first)) continue;
    T du = d[u].first;
    for (auto&& [v, c] : g[u]) {
      if (d[v].first == T(-1) || du + c < d[v].first) {
        d[v] = {du + c, u};
        Q.push(du + c, v);
      }
    }
  }
  return d;
}

/*
 * @brief ダイクストラ法(定数倍高速化)
 * @docs docs/shortest-path/dijkstra-fast.md
 **/

Back to top page