• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Dijkstra's algorithm

keverman Jan 11th, 2019 (edited) 92 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.

Top