# 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

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")
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
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

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:
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 = {}

queue = []

graph = initial_graph()

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

path[initial] = 0

while queue:
# find min distance which wasn't marked as current
key_min = queue
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

x = 'H'
print('The path between A to H')
print(x, end = '<-')
while True:
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<-```