How to implement Dijkstra’s shortest path algorithm in Python

In this Python tutorial, we are going to learn what is Dijkstra’s algorithm and how to implement this algorithm in Python.

Definition:- This algorithm is used to find the shortest route or path between any two nodes in a given graph.

Uses:-

1) The main use of this algorithm is that the graph fixes a source node and finds the shortest path to all other nodes present in the graph which produces a shortest path tree.

2) It can also be used to find the distance between source node to destination node by stopping the algorithm once the shortest route is identified.

 

        Implementation of Dijkstra’s Algorithm in Python

Algorithm of Dijkstra’s:

1 ) First, create a graph.

def initial_graph() :
    
    return {
            
        'A': {'B':1, 'C':4, 'D':2},
        'B': {'A':9, 'E':5},
        'C': {'A':4, 'F':15},
        'D': {'A':10, 'F':7},
        'E': {'B':3, 'J':7},
        'F': {'C':11, 'D':14, 'K':3, 'G':9},
        'G': {'F':12, 'I':4},
        'H': {'J':13},
        'I': {'G':6, 'J':7},
        'J': {'H':2, 'I':4},
        'K': {'F':6}
            
            
            
            }



2) Now, initialize the source node.

3) Assign a variable called path to find the shortest distance between all the nodes.

4) Assign a variable called adj_node to explore it’s adjacent or neighbouring nodes.

5) Assign a variable called queue to append the unvisited nodes and to remove the visited nodes.

6) Assign a variable called graph to implement the created graph.

initial = 'A' #2

path = {} #3

adj_node = {} #4

queue = [] #5

graph = initial_graph() #6

Create a loop called node such that every node in the graph is visited. Also, initialize the path to zero.

for node in graph:
    path[node] = float("inf")
    adj_node[node] = None
    queue.append(node)
    
path[initial] = 0

Now, create a while loop inside the queue to delete the visited nodes and also to find the minimum distance between the nodes.

while queue:

    key_min = queue[0]
    min_val = path[key_min]
    for n in range(1, len(queue)):
        if path[queue[n]] < min_val:
            key_min = queue[n]  
            min_val = path[key_min]
    cur = key_min
    queue.remove(cur)
    
    

    for i in graph[cur]:
        alternate = graph[cur][i] + path[cur]
        if path[i] > alternate:
            path[i] = alternate
            adj_node[i] = cur

Finally, assign a variable x for the destination node for finding the minimum distance between the source node and destination node.

x = 'H'
print('The path between A to H')
print(x, end = '<-')
while True:
    x = adj_node[x]
    if x is None:
        print("")
        break
    print(x, end='<-')

 

Python Code to find out the shortest path using Dijkstra’s Algorithm

def initial_graph() :
    
    return {
            
        'A': {'B':1, 'C':4, 'D':2},
        'B': {'A':9, 'E':5},
        'C': {'A':4, 'F':15},
        'D': {'A':10, 'F':7},
        'E': {'B':3, 'J':7},
        'F': {'C':11, 'D':14, 'K':3, 'G':9},
        'G': {'F':12, 'I':4},
        'H': {'J':13},
        'I': {'G':6, 'J':7},
        'J': {'H':2, 'I':4},
        'K': {'F':6}
            
            
            
            }



print(initial_graph())
    

initial = 'A'

path = {}

adj_node = {}

queue = []

graph = initial_graph()

for node in graph:
    path[node] = float("inf")
    adj_node[node] = None
    queue.append(node)
    
path[initial] = 0

while queue:
    # find min distance which wasn't marked as current
    key_min = queue[0]
    min_val = path[key_min]
    for n in range(1, len(queue)):
        if path[queue[n]] < min_val:
            key_min = queue[n]  
            min_val = path[key_min]
    cur = key_min
    queue.remove(cur)
    print(cur)
    

    for i in graph[cur]:
        alternate = graph[cur][i] + path[cur]
        if path[i] > alternate:
            path[i] = alternate
            adj_node[i] = cur
            
            
x = 'H'
print('The path between A to H')
print(x, end = '<-')
while True:
    x = adj_node[x]
    if x is None:
        print("")
        break
    print(x, end='<-')

Output:

# Creating a graph

{'A': {'B': 1, 'C': 4, 'D': 2}, 'B': {'A': 9, 'E': 5}, 'C': {'A': 4, 'F': 15}, 'D': {'A': 10, 'F': 7}, 'E': {'B': 3, 'J': 7}, 'F': {'C': 11, 'D': 14, 'K': 3, 'G': 9}, 'G': {'F': 12, 'I': 4}, 'H': {'J': 13}, 'I': {'G': 6, 'J': 7}, 'J': {'H': 2, 'I': 4}, 'K': {'F': 6}}

# Exploring all the adjacent nodes
A
B
D
C
E
F
K
J
H
I
G

# Shortest Path between Source node and Destination Node
The path between A to H
H<-J<-E<-B<-A<-

 

You can also read,

How the Bubble Sorting technique is implemented in Python

How to implement a Queue data structure in Python

 

Leave a Reply

Your email address will not be published. Required fields are marked *