Dijkstra Algorithm in Python

Photo by Alina Grubnyak on Unsplash

It is a well-known Algorithm used to find the shortest distance and shortest path from a single source node to all other nodes in a graph. This algorithm only works on graphs, where there are no negative cycles in them (i.e. a cycle whose edges sum to a negative value).

The algorithm

1. Create a set “seen” to keep track of visited nodes.
2. Create a dictionary “parentsMap” for parents map to reconstruct the path after the execution of the algorithm.
3. Create a dictionary “nodeCosts” for keeping track of minimum costs for reaching different nodes from the source node, and initialize the cost for the source node as 0.
4. Create a priority queue data structure (in python use heapq module with list) and push a tuple (0, source node) in the Priority Queue (heap), representing (the cost to the node from the source node, the node itself).
5. loop inside a while loop until there is nothing in the priority queue. while looping, pop the node with minimum cost.
6. loop through all of the pop node’s adjacent nodes. if they have not been explored before, and have total costs minimum than the cost in the “nodeCosts” add them too to the priority queue and update the “parentsMap”.
7. Reconstruct the path from the “parentsMap”.

The CODE

Reconstruction of a path using parentsMap is trivial.

Extras

• If we just want the shortest path from some source node to some other node, say “end node”, we can early exit from while loop (when we are popping the minimum costs nodes from the heap and that node, happens to be the end node).
• Above implementation is a lazy implementation of the Dijkstra algorithm (we are adding nodes to the heap but there may be that same node in that heap with a higher cost, which is coming from a different path) there is also eager implementation which one can find at my GitHub.

If you found any error anywhere in the blog or want to suggest something to add to it, consider commenting the same.

Thanks for reading.