Processing math: 100%
My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Dijkstra with Fibonacci Heap

コードについての説明

Dijkstra 法を Fibonacci Heap を用いて高速化したアルゴリズム.
すでにフィボナッチヒープ内にある頂点についての最短距離の更新はキー値減算を用いることで 1 回あたりならし O(1) で行えるため, 新たに要素を insert する必要はない. 結果 insert および delete は n 回となるので計算量は O(nlogn+m) となる.
元論文は "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms" [Fredman, Tarjan 1984]

時間計算量: O(nlogn+m)

コード

  1. template<typename _Key, typename _Tp> class FibonacciHeap
  2. {
  3. public:
  4.     using data_type = pair<_Key, _Tp>;
  5.     class node
  6.     {
  7.     public:
  8.         data_type _data;
  9.         unsigned short int _child;
  10.         bool _mark;
  11.         node *_par, *_prev, *_next, *_ch_last;
  12.         node(data_type&& data) : _data(move(data)), _child(0), _mark(false),
  13.             _par(nullptr), _prev(nullptr), _next(nullptr), _ch_last(nullptr){}
  14.         inline const _Key& get_key() const noexcept { return _data.first; }
  15.         void insert(node *cur){
  16.             if(_ch_last) insert_impl(cur, _ch_last);
  17.             else _ch_last = cur, _ch_last->_prev = _ch_last->_next = _ch_last;
  18.             ++_child, cur->_par = this;
  19.         }
  20.         void erase(node *cur){
  21.             if(cur == cur->_prev){
  22.                 _ch_last = nullptr;
  23.             }else{
  24.                 erase_impl(cur);
  25.                 if(cur == _ch_last) _ch_last = cur->_prev;
  26.             }
  27.             --_child, cur->_par = nullptr;
  28.         }
  29.     };
  30.  
  31. private:
  32.     size_t _size;
  33.     node *_minimum;
  34.     vector<node*> rank;
  35.  
  36.     static void insert_impl(node *cur, node *next){
  37.         cur->_prev = next->_prev, cur->_next = next;
  38.         cur->_prev->_next = cur, next->_prev = cur;
  39.     }
  40.     static void erase_impl(node *cur){
  41.         cur->_prev->_next = cur->_next, cur->_next->_prev = cur->_prev;
  42.     }
  43.     void root_insert(node *cur){
  44.         if(_minimum){
  45.             insert_impl(cur, _minimum);
  46.             if(cur->get_key() < _minimum->get_key()) _minimum = cur;
  47.         }else{
  48.             _minimum = cur, _minimum->_prev = _minimum->_next = _minimum;
  49.         }
  50.     }
  51.     void root_erase(node *cur){
  52.         if(cur == cur->_prev) _minimum = nullptr;
  53.         else erase_impl(cur);
  54.     }
  55.     void _delete(node *cur){
  56.         root_erase(cur);
  57.         delete cur;
  58.     }
  59.     template<typename Key, typename Data>
  60.     node *_push(Key&& key, Data&& data){
  61.         ++_size;
  62.         data_type new_data(forward<Key>(key), forward<Data>(data));
  63.         node* new_node = new node(move(new_data));
  64.         root_insert(new_node);
  65.         return new_node;
  66.     }
  67.     void _pop(){
  68.         assert(_size > 0);
  69.         --_size;
  70.         if(_size == 0){
  71.             _delete(_minimum);
  72.             return;
  73.         }
  74.         if(_minimum->_ch_last){
  75.             for(node *cur = _minimum->_ch_last->_next;;){
  76.                 node *next = cur->_next;
  77.                 _minimum->erase(cur), root_insert(cur);
  78.                 if(!_minimum->_ch_last) break;
  79.                 cur = next;
  80.             }
  81.         }
  82.         node *next_minimum = _minimum->_next;
  83.         for(node*& cur : rank) cur = nullptr;
  84.         for(node *cur = next_minimum; cur != _minimum;){
  85.             if(cur->get_key() < next_minimum->get_key()) next_minimum = cur;
  86.             node *next = cur->_next;
  87.             unsigned int deg = cur->_child;
  88.             if(rank.size() <= deg) rank.resize(deg + 1, nullptr);
  89.             while(rank[deg]){
  90.                 if(cur->get_key() < rank[deg]->get_key() || cur == next_minimum){
  91.                     root_erase(rank[deg]), cur->insert(rank[deg]);
  92.                 }else{
  93.                     root_erase(cur), rank[deg]->insert(cur);
  94.                     cur = rank[deg];
  95.                 }
  96.                 rank[deg++] = nullptr;
  97.                 if(rank.size() <= deg) rank.resize(deg + 1, nullptr);
  98.             }
  99.             rank[deg] = cur;
  100.             cur = next;
  101.         }
  102.         _delete(_minimum);
  103.         _minimum = next_minimum;
  104.     }
  105.     void _decrease_key(node *cur, const _Key& key){
  106.         assert(!(key < (_Key)0));
  107.         node *change = ((cur->_data.first -= key) < _minimum->get_key()) ? cur : nullptr;
  108.         if(!cur->_par || !(cur->get_key() < cur->_par->get_key())){
  109.             if(change) _minimum = change;
  110.             return;
  111.         }
  112.         while(true){
  113.             node *next = cur->_par;
  114.             next->erase(cur), root_insert(cur);
  115.             cur->_mark = false, cur = next;
  116.             if(!cur->_par) break;
  117.             if(!cur->_mark){
  118.                 cur->_mark = true;
  119.                 break;
  120.             }
  121.         }
  122.         if(change) _minimum = change;
  123.     }
  124.     void clear_dfs(node *cur){
  125.         if(cur->_ch_last){
  126.             for(node *_cur = cur->_ch_last->_next;;){
  127.                 node *next = _cur->_next;
  128.                 if(_cur == cur->_ch_last){
  129.                     clear_dfs(_cur);
  130.                     break;
  131.                 }else{
  132.                     clear_dfs(_cur);
  133.                 }
  134.                 _cur = next;
  135.             }
  136.         }
  137.         delete cur;
  138.         return;
  139.     }
  140.     void _clear(){
  141.         if(!_minimum) return;
  142.         for(node *cur = _minimum->_next;;){
  143.             node *next = cur->_next;
  144.             if(cur == _minimum){
  145.                 clear_dfs(cur);
  146.                 break;
  147.             }else{
  148.                 clear_dfs(cur);
  149.             }
  150.             cur = next;
  151.         }
  152.     }
  153.  
  154. public:
  155.     FibonacciHeap() noexcept : _size(0u), _minimum(nullptr){}
  156.     // ~FibonacciHeap(){ _clear(); }
  157.     inline bool empty() const noexcept { return (_size == 0); }
  158.     inline size_t size() const noexcept { return _size; }
  159.     inline const data_type& top() const noexcept { return _minimum->_data; }
  160.     template<typename Key, typename Data>
  161.     node *push(Key&& key, Data&& data){ return _push(forward<Key>(key), forward<Data>(data)); }
  162.     void pop(){ _pop(); }
  163.     void decrease_key(node *cur, const _Key& key){ _decrease_key(cur, key); }
  164.     void clear(){ _clear(); _size = 0; rank.~vector<node*>(); }
  165. };
  166.  
  167. template<typename T> class Dijkstra {
  168. public:
  169.     struct edge{
  170.         int to; T cost;
  171.     };
  172.     const int V;
  173.     vector<vector<edge> > G;
  174.     vector<T> d;
  175.     FibonacciHeap<T, int> fheap;
  176.     typename FibonacciHeap<T, int>::node** keep;
  177.     Dijkstra(int node_size) : V(node_size), G(V), d(V, numeric_limits<T>::max()),
  178.         keep(new typename FibonacciHeap<T, int>::node*[V]){}
  179.     // ~Dijkstra(){
  180.         // delete[] keep;
  181.     // }
  182.     // 有向グラフの場合
  183.     void add_edge(int u,int v,T cost){
  184.         G[u].pb((edge){v, cost});
  185. 	}
  186.     void solve(int s){
  187.         d[s] = 0;
  188.         keep[s] = fheap.push(0, s);
  189.         while(!fheap.empty()){
  190.             int v = fheap.top().second;
  191.             fheap.pop();
  192.             for(autoamp; w : G[v]){
  193.                 if(d[w.to] > d[v] + w.cost){
  194.                     if(d[w.to] == numeric_limits<T>::max()){
  195.                         keep[w.to] = fheap.push(d[v] + w.cost, w.to);
  196.                     }else{
  197.                         fheap.decrease_key(keep[w.to], d[w.to] - (d[v] + w.cost));
  198.                     }
  199.                     d[w.to] = d[v] + w.cost;
  200.                 }
  201.             }
  202.         }
  203.     }
  204. };

verify 用の問題

AOJ : Single Source Shortest Path 提出コード