How to Implement Dijkstra’s Algorithm Efficiently Efficiently using C++ STL?
See this code. Focus on Function part of Dijkstra() part. It’s simple and efficiently implemented.
1 Like
Try this link. It includes an efficient priority queue C++ STL implementation of Dijkstra and is quite efficient
Hope it helps
Dijkstra’s Algorithm can be implemented quite efficiently by making use of a min-heap. In C++, STL provides you with a max-heap implementation (default), given by priority_queue. You can also create a min-heap. Refer to http://stackoverflow.com/questions/2439283/how-can-i-create-min-stl-priority-queue for more information.
http://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/ gives a good description on how Dijkstra’s Algorithm works. We prioritize the node which has the minimum distance from the
start node and use BFS traversal of graph.
The rough pseudocode follows. Note that all distances are in reference of source node.
-
Assign all nodes distances infinity
-
Maintain a min heap with entry as the distance of source node (which is zero) and the node as key-value pair. Distance should be the key.
-
While the priority queue is not empty, iterate over all nodes directly connected to the current node. If the distance of the ith node is greater than the sum of distance of the current node and the distance
between the ith node and current node, assign distance of ith node = distance of current node + distance
between current node and ith node, and push key-value pair (distance of ith node, ith node) in queue. -
Finally print the distance of the destination node.
Refer to the link for a more detailed explanation.
If this answers your question please mark it as accepted.
2 Likes
If this answers your question please mark it as accepted.
No need to mention in every answer.
1 Like
I have seen others do it as well. No harm in doing it myself.
What is mean of below lines:
d.resize(G.size(),INT_MAX);
priority_queue<pair<int,int>, vector<pair<int,int> >, Comparator> Q;