# Implement Dijkstra Algorithm using Python- Single source path

Dijkstra algorithm is used to find the shortest paths between nodes in a graph. Given a source node in the graph, the algorithm finds the shortest path between that node and every other. In this tutorial, we are going to see how to implement the Dijkstra algorithm using python.

In the BFS traversal algorithm, we have a constant that our graph’s edges should be the same cost. But Dijkstra algorithm the edges should not be the mandatory same cost. The drawback of the Dijkstra algorithm is if the cost of the edge is negative then this algorithm may or may not work. To solve this issue we can use another algorithm that is the Bellman-Ford algorithm.

##### Read More: Detecting Cycle in a Graph using DFS Algorithm in Python

Let’s see the algorithm of the Dijkstra code.

## Algorithm of Dijkstra

• Maintain a set of pressed node
• Assign all nodes with distance value is equal to infinite except the source node. Assign zero in source node.
• Repeat the following steps. (Unless the all vertices are incuded)
• Pick the min value of vertics which is not already pressed.
• Include the seleted node in the pressed set
• Update the all adjacent node distaces if the new distance is greater than old distance else skip.

Let’s see this graph. In this tutorial, we will implement this graph that is an undirected graph, and also find the shortest path.

Well, let’s make this graph into an adjacency list in python. To do that I will use python dictionary data structure. Let’s see the pieces of code.

``````graph = {
"A": {"B": 2, "C": 4},
"B": {"A": 2, "C": 3, "D": 8},
"C": {"A": 4, "B": 3, "D": 2, "E": 5},
"D": {"B": 8, "C": 2, "F": 22, "E": 11},
"E": {"C": 5, "D": 11, "F": 1},
"F": {"D": 22, "E": 1},
}``````

Well, to implement this algorithm we need a built-in module that is sys. Also, we need a heap module. Let’s import these modules.

``````import sys
from heapq import heapify, heappush, heappop``````

Now see the code of the Dijkstra algorithm’s function. I will explain you later.

``````def dijkstra(graph, source, destination):
inf = sys.maxsize
node_data = {}
for node in graph.keys():
node_data[node] = {'cost': inf, 'pred': []}

node_data[source]['cost'] = 0
visited = []
temp = source

for i in range((len(graph.keys())-1)):
if temp not in visited:
visited.append(temp)
min_heap = []
for j in graph[temp]:
if j not in visited:
cost = node_data[temp]['cost'] + graph[temp][j]
if cost < node_data[j]['cost']:
node_data[j]['cost'] = cost
node_data[j]['pred'] = node_data[temp]['pred'] + \
list(temp)
heappush(min_heap, (node_data[j]['cost'], j))
heapify(min_heap)
temp = min_heap[0][1]
# print(temp)
# return
print("Sortest Distance : ", str(node_data[destination]['cost']))
print("Sortest Path : ", str(
node_data[destination]['pred'] + list(destination)))``````

Well, this function takes three parameters. There is the graph another one is the source node and the last one is the destination node. Inside this function, first I have taken two variables and then done initial tasks. The initial task is according to the algorithm is to set all vertices cost is equal to infinite and the predecessor of a node is an empty list. Then assign the source node into a temporary variable.

Well, now you have to execute a loop from zero to before the number of nodes. Inside the loop, first, you have to check the temporary node is visited or not. Then take a list for min-heap.

Now you have to execute another loop. Inside the loop, you have to check the unvisited neighbor. After then you have to calculate the cost. If the cost is greater than the neighbor node then reassign the cost value. Then push the neighbor into the heap as well cost. Finally, call the heapify function and reassign the temp value with the heap’s min value.

Now print the shortest distances as well the shortest path using the destination node.

## Full Code

``````

import sys
from heapq import heapify, heappush, heappop

def dijkstra(graph, source, destination):
inf = sys.maxsize
node_data = {}
for node in graph.keys():
node_data[node] = {'cost': inf, 'pred': []}

node_data[source]['cost'] = 0
visited = []
temp = source

for i in range((len(graph.keys())-1)):
if temp not in visited:
visited.append(temp)
min_heap = []
for j in graph[temp]:
if j not in visited:
cost = node_data[temp]['cost'] + graph[temp][j]
if cost < node_data[j]['cost']:
node_data[j]['cost'] = cost
node_data[j]['pred'] = node_data[temp]['pred'] + \
list(temp)
heappush(min_heap, (node_data[j]['cost'], j))
heapify(min_heap)
temp = min_heap[0][1]
# print(temp)
# return
print("Sortest Distance : ", str(node_data[destination]['cost']))
print("Sortest Path : ", str(
node_data[destination]['pred'] + list(destination)))

graph = {
"A": {"B": 2, "C": 4},
"B": {"A": 2, "C": 3, "D": 8},
"C": {"A": 4, "B": 3, "D": 2, "E": 5},
"D": {"B": 8, "C": 2, "F": 22, "E": 11},
"E": {"C": 5, "D": 11, "F": 1},
"F": {"D": 22, "E": 1},
}

source = "A"
destination = "E"
dijkstra(graph, source, destination)``````