Advertisement
keverman

Dijkstra's algorithm

Jan 11th, 2019 (edited)
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  1. struct edge {};
  2.  
  3. struct pq_node
  4. {
  5.     int node;
  6.     ll distance;
  7.  
  8.     pq_node() {}
  9.     pq_node(int _node, ll _distance)
  10.     {
  11.         node = _node, distance = _distance;
  12.     }
  13. };
  14.  
  15. struct pq_node_comp
  16. {
  17.     bool operator()(pq_node& l, pq_node& r)
  18.     {
  19.         return l.distance < r.distance;
  20.     }
  21. };
  22.  
  23. std::vector<ll> Dijkstra(int src, std::vector<std::vector<edge>>& edges)
  24. {
  25.     std::vector<ll> dist(size(), ll_inf);
  26.     dist[src] = 0;
  27.  
  28.     std::priority_queue<pq_node, std::vector<pq_node>, pq_node_comp> PQ;
  29.     PQ.push(pq_node(src, 0));
  30.  
  31.     while (!PQ.empty())
  32.     {
  33.         pq_node from = PQ.top();
  34.         PQ.pop();
  35.  
  36.         for (edge& e : edges[from.node])
  37.             if (from.distance + e.weight < dist[e.to])
  38.                 PQ.push(pq_node(e.to, dist[e.to] = from.distance + e.weight));
  39.     }
  40.  
  41.     return dist;
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement