 # Implement Dijkstra’s Algorithm Efficiently.

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.