Line data    Source code

       1             : #include "Alg/ShortestPath/Dijkstra.hpp"
       2             : 
       3             : #include <chrono>
       4             : #include <iostream>
       5             : #include <queue>
       6             : #include <utility>
       7             : 
       8             : #include "Alg/BinaryHeap.hpp"
       9             : 
      10             : using namespace std;
      11             : using namespace Alg;
      12             : using namespace Alg::ShortestPath;
      13             : 
      14             : typedef Graph::Node         Node;
      15             : typedef Graph::Edge::Weight Weight;
      16             : typedef Graph::Edge         Edge;
      17             : 
      18             : typedef BinaryHeap<pair<Weight, Node>> MinPriorityQueue;
      19             : 
      20          42 : bool Dijkstra::isStart(Node u) const {
      21          42 :     return sSet.count(u);
      22             : }
      23             : 
      24          14 : void Dijkstra::solveList(const Graph &G, const list<Node> &sList) {
      25             :     // Initialize
      26          14 :     Node maxNode = 0;
      27       15356 :     for(const Node &u: G.getNodes()) {
      28       15369 :         maxNode = max(maxNode, u);
      29             :     }
      30          14 :     dist = vector<Weight>(maxNode + 1, Edge::WEIGHT_INF);
      31          14 :     prev = vector<Edge>(maxNode + 1, Graph::EDGE_INVALID);
      32             : 
      33          14 :     sSet.clear();
      34          14 :     sSet.insert(sList.begin(), sList.end());
      35             : 
      36             :     // Run
      37          14 :     vector<MinPriorityQueue::Element *> elements(dist.size());
      38             : 
      39          28 :     MinPriorityQueue Q;
      40          14 :     Q.reserve(dist.size());
      41             : 
      42          28 :     for(const Node &s: sList) {
      43          14 :         dist[s]     = 0;
      44          14 :         elements[s] = &Q.push({0, s});
      45             :     }
      46             : 
      47       14730 :     while(!Q.empty()) {
      48       14716 :         const auto &[du, u] = Q.top();
      49       14716 :         Q.pop();
      50       34083 :         for(const Edge &e: G.getAdj(u)) {
      51       19367 :             Weight  c_    = du + e.w;
      52       19367 :             Weight &distV = dist[e.v];
      53       19367 :             if(c_ < distV) {
      54       14853 :                 MinPriorityQueue::Element *&elV = elements[e.v];
      55       14853 :                 if(elV)
      56         151 :                     elV->decreaseKey({c_, e.v});
      57             :                 else
      58       14702 :                     elV = &Q.push({c_, e.v});
      59       14853 :                 distV     = c_;
      60       14853 :                 prev[e.v] = e;
      61             :             }
      62             :         }
      63             :     }
      64          14 : }
      65             : 
      66          44 : Edge Dijkstra::getPrev(Node d) const {
      67          44 :     return prev.at(d);
      68             : }
      69             : 
      70          36 : Weight Dijkstra::getPathWeight(Node d) const {
      71          36 :     return dist.at(d);
      72             : }
      73             : 
      74             : // clang-format off
      75           0 : bool Dijkstra::hasVisited(Node u) const {
      76           0 : #pragma GCC diagnostic push
      77           0 : #pragma GCC diagnostic ignored "-Wfloat-equal"
      78           0 :     return (dist.at(u) != Edge::WEIGHT_INF);
      79           0 : #pragma GCC diagnostic pop
      80             : }
      81             : // clang-format on