Implementing Dijkstra’s Algorithm in Python

Whenever we need to represent and store connections or links between elements, we use data structures known as graphs. In a graph, we have nodes (vertices) and edges. Nodes are objects (values), and edges are the lines that connect nodes. In python, we represent graphs using a nested dictionary. We represent nodes of the graph as the key and its connections as the value. We often need to find the shortest distance between these nodes, and we generally use Dijkstra’s Algorithm in python.  A graph in general looks like this-

Dijkstra's Algorithm Python

So, Dijkstra’s Algorithm is used to find the shortest distance between the source node and the target node. The approach that Dijkstra’s Algorithm follows is known as the Greedy Approach. Although today’s point of discussion is understanding the logic and implementation of Dijkstra’s Algorithm in python, if you are unfamiliar with terms like Greedy Approach and Graphs, bear with us for some time, and we will try explaining each and everything in this article. 

Concept Behind Dijkstra’s Algorithm 

What is Greedy Approach? 

In the Introduction section, we told you that Dijkstra’s Algorithm works on the greedy approach, so what is this Greedy approach?

In Laymen’s terms, the Greedy approach is the strategy in which we chose the best possible choice available, assuming that it will lead us to the best solution.  

Think about it in this way, we chose the best solution at that moment without thinking much about the consequences in the future.  

Algorithm: 

Step 1: Make a temporary graph that stores the original graph’s value and name it as an unvisited graph. Also, initialize a list called a path to save the shortest path between source and target. 

Dijkstra's algorithm python

Step 2: We need to calculate the Minimum Distance from the source node to each node.

Initially, mark total_distance for every node as infinity (∞) and the source node mark total_distance as 0, as the distance from the source node to the source node is 0. Also, mark this source node as current_node. 

Dijkstra's algorithm python
The source node/ current_node is ‘A’, mark it as 0.

Step 3: From the current_node, select the neighbor nodes (nodes that are directly connected) in any random order. Check if the current value of that node is (initially it will be (∞)) is higher than (the value of the current_node + value of the edge that connects this neighbor node with current_node ).

If yes, then replace the importance of this neighbor node with the value of the current_node + value of the edge that connects this neighbor node with current_node. Repeat this process for all the neighboring nodes of the current node

Dijkstra's algorithm python
At C, as 2 < ∞, update the value of C from ∞ to 2.
Dijkstra's algorithm python
At B, as 5 < ∞, update the value of B from ∞ to 5.

Step 4: After we have updated all the neighboring nodes of the current node’s values, it’s time to delete the current node from the unvisited_nodes.

From all those nodes that were neighbors of the current node, the neighbor chose the neighbor with the minimum_distance and set it as current_node. 

Dijkstra's algorithm python
At D (the path is A->C->D), 9 (7+2) is less than ∞, update the value from ∞ to 9.

Step 5: Repeat steps 3 and 4 until and unless all the nodes in unvisited_visited nodes have been visited.  

Once all the nodes have been visited, we will get the shortest distance from the source node to the target node.  

Dijkstra's algorithm python
When we again arrive at D (this time the path is A->B ->D), the value of D becomes 8.
Dijkstra's algorithm python
Finally, at E, 15 < ∞, So the distance will update from ∞ to 15.

The output we got here is 15.

Now that we have the idea of how Dijkstra’s Algorithm works let us make a python program for it and verify our output from above.

Implementing Dijkstra’s Algorithm in Python 

import math

def Dijkstra(graph,source,target):
    
    # These are all the nodes which have not been visited yet
    unvisited_nodes=graph
    # It will store the shortest distance from one node to another
    shortest_distance={}
    # This will store the Shortest path between source and target node 
    route=[] 
    # It will store the predecessors of the nodes
    predecessor={}
    
    # Iterating through all the unvisited nodes
    for nodes in unvisited_nodes:
        
    # Setting the shortest_distance of all the nodes as infinty
        shortest_distance[nodes]=math.inf
        
    # The distance of a point to itself is 0.
    shortest_distance[source]=0
    
    # Running the loop while all the nodes have been visited
    while(unvisited_nodes):
        
        # setting the value of min_node as None
        min_Node=None
        
        # iterating through all the unvisited node
        for current_node in unvisited_nodes: 
            
        # For the very first time that loop runs this will be called
            if min_Node is None:
            
            # Setting the value of min_Node as the current node
                min_Node=current_node
                
            elif shortest_distance[min_Node] > shortest_distance[current_node]:
                
            # I the value of min_Node is less than that of current_node, set 
            #min_Node as current_node

                min_Node=current_node
                
        # Iterating through the connected nodes of current_node (for # 
        example, a is connected with b and c having values 10 and 3 
        # respectively) and the weight of the edges

        for child_node,value in unvisited_nodes[min_Node].items():

            # checking if the value of the current_node + value of the edge 
            # that connects this neighbor node with current_node
            # is lesser than the value that distance between current nodes 
            # and its connections
            if value + shortest_distance[min_Node] < shortest_distance[child_node]:  
                
     # If true  set the new value as the minimum distance of that connection
                shortest_distance[child_node] = value + shortest_distance[min_Node]
                
           # Adding the current node as the predecessor of the child node
                predecessor[child_node] = min_Node
        
        # After the node has been visited (also known as relaxed) remove it from unvisited node
        unvisited_nodes.pop(min_Node)
        
    # Till now the shortest distance between the source node and target node 
    # has been found. Set the current node as the target node 
    node = target
    
    # Starting from the goal node, we will go back to the source node and 
# see what path we followed to get the smallest distance
    while node != source:
        
        # As it is not necessary that the target node can be reached from # the source node, we must enclose it in a try block
        try:
            route.insert(0,node)
            node = predecessor[node]
        except Exception:
            print('Path not reachable')
            break
    # Including the ssource in the path
    route.insert(0,source)
    
    # If the node has been visited,
    if shortest_distance[target] != math.inf:
        # print the shortest distance and the path taken
        print('Shortest distance is ' + str(shortest_distance[target]))
        print('And the path is ' + str(route))
    # Remove the below comment if you want to show the the shortest distance 
    #from source to every other node
    # print(shortest_distance)

graph = {'a':{'b':5,'c':2},'b':{'c':1,'d':3},'c':{'b':3,'d':7},'d':{'e':7},'e':{'d':9}}
#Calling the function with source as 'a' and target as 'e'.
Dijkstra(graph,'a','e')

Output-

Shortest distance is 15 
And the path is ['a', 'b', 'd', 'e']

The answer is same that we got from the algorithm.

Must Read:

Conclusion 

Dijkstra’s Algorithm in python comes very handily when we want to find the shortest distance between source and target. It can work for both directed and undirected graphs. The limitation of this Algorithm is that it may or may not give the correct result for negative numbers. In Google Maps, for finding the shortest route between one source to another, we use Dijkstra’s Algorithm. Another application is in networking, where it helps in sending a packet from source to destination.

Try to run the programs on your side and let us know if you have any queries.

Happy Coding!

Leave a Reply