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

• View this file on GitHub
• Last update: 2021-02-11 00:13:40+09:00
• Include: #include "shortest-path/dijkstra-skew-heap.hpp"

ダイクストラ法(Skew Heap)

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

概要

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

使い方

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

Depends on

• Static Graph (graph/static-graph.hpp)

Verified with

• verify/verify-yosupo-graph/yosupo-shortest-path-4.test.cpp

Code

#pragma once

#include "../graph/static-graph.hpp"

template <typename T>
struct SkewHeap {
  struct alignas(32) Node {
    T key;
    int p, l, r;
    Node(const T& k = T()) : key(k), p(-1), l(-1), r(-1) {}
  };

  vector<Node> v;
  int rt = -1;

  SkewHeap(int n) : v(n) {}

  int meld(int x, int y) {
    if (x == -1 || y == -1) return x == -1 ? y : x;
    if (v[x].key > v[y].key) swap(x, y);
    v[x].r = meld(v[x].r, y);
    v[v[x].r].p = x;
    swap(v[x].l, v[x].r);
    return x;
  }

  void pop() { rt = meld(v[rt].l, v[rt].r); }

  void update(int x, const T& k) {
    Node& n = v[x];
    v[x].key = k;
    if (x == rt) return;
    Node& p = v[n.p];
    if (p.key <= k) return;
    (p.l == x ? p.l : p.r) = -1;
    n.p = -1;
    rt = meld(rt, x);
  }

  bool empty() { return rt == -1; }
};

template <typename T>
vector<pair<T, int>> dijkstra_restore(StaticGraph<T>& g, int start = 0) {
  int N = (int)g.size();
  using P = pair<T, int>;
  vector<P> d(N, P{-1, -1});
  SkewHeap<T> Q(N);
  d[start].first = 0;
  Q.v[start].key = 0;
  Q.rt = start;
  while (!Q.empty()) {
    T dc = Q.v[Q.rt].key;
    int cur = Q.rt;
    Q.pop();
    for (auto dst : g[cur]) {
      if (d[dst].first == T(-1)) {
        d[dst] = P{dc + dst.cost, cur};
        Q.v[dst].key = dc + dst.cost;
        Q.rt = Q.meld(Q.rt, dst);
      } else if (dc + dst.cost < d[dst].first) {
        d[dst] = P{dc + dst.cost, cur};
        Q.update(dst, dc + dst.cost);
      }
    }
  }
  return d;
}
/*
 * @brief ダイクストラ法(Skew Heap)
 * @docs docs/shortest-path/dijkstra-skew-heap.md
**/

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

#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 4 "shortest-path/dijkstra-skew-heap.hpp"

template <typename T>
struct SkewHeap {
  struct alignas(32) Node {
    T key;
    int p, l, r;
    Node(const T& k = T()) : key(k), p(-1), l(-1), r(-1) {}
  };

  vector<Node> v;
  int rt = -1;

  SkewHeap(int n) : v(n) {}

  int meld(int x, int y) {
    if (x == -1 || y == -1) return x == -1 ? y : x;
    if (v[x].key > v[y].key) swap(x, y);
    v[x].r = meld(v[x].r, y);
    v[v[x].r].p = x;
    swap(v[x].l, v[x].r);
    return x;
  }

  void pop() { rt = meld(v[rt].l, v[rt].r); }

  void update(int x, const T& k) {
    Node& n = v[x];
    v[x].key = k;
    if (x == rt) return;
    Node& p = v[n.p];
    if (p.key <= k) return;
    (p.l == x ? p.l : p.r) = -1;
    n.p = -1;
    rt = meld(rt, x);
  }

  bool empty() { return rt == -1; }
};

template <typename T>
vector<pair<T, int>> dijkstra_restore(StaticGraph<T>& g, int start = 0) {
  int N = (int)g.size();
  using P = pair<T, int>;
  vector<P> d(N, P{-1, -1});
  SkewHeap<T> Q(N);
  d[start].first = 0;
  Q.v[start].key = 0;
  Q.rt = start;
  while (!Q.empty()) {
    T dc = Q.v[Q.rt].key;
    int cur = Q.rt;
    Q.pop();
    for (auto dst : g[cur]) {
      if (d[dst].first == T(-1)) {
        d[dst] = P{dc + dst.cost, cur};
        Q.v[dst].key = dc + dst.cost;
        Q.rt = Q.meld(Q.rt, dst);
      } else if (dc + dst.cost < d[dst].first) {
        d[dst] = P{dc + dst.cost, cur};
        Q.update(dst, dc + dst.cost);
      }
    }
  }
  return d;
}
/*
 * @brief ダイクストラ法(Skew Heap)
 * @docs docs/shortest-path/dijkstra-skew-heap.md
**/

Back to top page