daily pastebin goal
42%
SHARE
TWEET

Dijkstra's algorithm

keverman Jan 11th, 2019 (edited) 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // STL Priority Queue Dijkstra implementation
  2. // Requires weighted graph
  3. // Edge can be found in an appropriate graph class
  4.  
  5. struct pq_node
  6. {
  7.     int node;
  8.     ll distance;
  9.    
  10.     pq_node() {}
  11.     pq_node(int _node, ll _distance)
  12.     {
  13.         node = _node, distance = _distance;
  14.     }
  15. };
  16.  
  17. struct pq_node_comp
  18. {
  19.     bool operator()(pq_node &l, pq_node &r)
  20.     {
  21.         return l.distance < r.distance;
  22.     }
  23. };
  24.  
  25. std::vector<ll> Dijkstra(int src)
  26. {
  27.     std::vector<ll> dist(size(), ll_inf);
  28.     dist[src] = 0;
  29.    
  30.     std::priority_queue<pq_node, std::vector<pq_node>, pq_node_comp> PQ;
  31.     PQ.push(pq_node(src, 0));
  32.    
  33.     while(!PQ.empty())
  34.     {
  35.         pq_node from = PQ.top();
  36.         PQ.pop();
  37.        
  38.         for(edge &e : edges[from.node])
  39.             if(from.distance + e.weight < dist[e.to])
  40.                 PQ.push(pq_node(e.to, dist[e.to] = from.distance + e.weight));
  41.     }
  42.    
  43.     return dist;
  44. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top