Python

Dijkstra’s Algorithm

3 years ago
by Shekhar Pandey
We sometimes need to find out the links between two different corners, and then we need the graph. In a simple example, if we want to go from one place to another place, then the Google maps show all the different ways but highlight the shortest path to reach your destination. But, if you change your path while using Google Map, then it predicts a new path according to your current location to your destination. So, all these happens through the algorithm which we called Dijkstra’s Algorithm. Dijkstra’s Algorithm finds the shortest path among the nodes.

In the graph, there are nodes and edges. The nodes are the values and the edges are the path or lines which create links between the two nodes. In Python, we can implement the nodes and edges using the nested dictionary. We can represent the nodes as a key and all the paths from that node to other nodes as a value of that particular key.

Dijkstra’s Algorithm is used to find the shortest path between the source node and the target node. The approach this algorithm is used called the Greedy approach. So, in this article, we are going to understand the concepts of Dijkstra’s Algorithm and how we can implement it using Python programming.

Dijkstra’s Algorithm as we said before, is using the concept of the Greedy approach. We can understand the greedy approach in a normal term which finds the optimal solution from the available options.

Algorithm Steps

  1. We first initialize the source node value 0 and other adjacent nodes values as infinite.
  2. Insert the source node and the distance value as a pair < node, dist > in the dictionary. For example, the source node value pair will be <S, 0>. The S represents the node name and 0 is the distance value. The value 0 is because we initialize the source node value 0.
  3. The Loop will continue till DICTIONARY, not null (or not empty).
  4. We assigned any pair <node, dist> from the DICTIONARY to current_source_node based on the following condition:

The node distance value should be less than the among available nodes distance values. After that, remove that from the dictionary list because that is now current_source_node.

  1. For each adjacent_link_node to the current_source_node do
  2. If ( dist [ adjacent_link_node ] > edge value from current_source_node to adjacent node+ dist [ current_source_node ] )
  3. dist [ adjacent_link_node ] = edge value from current_source_node to adjacent node + dist [ current_source_node ]
  4. Then update the DICTIONARY with pair <adjacent_link_node_name, dist [ adjacent_link_node,] >

Dijkstra’s Algorithm Steps

Dijkstra’s Algorithm is used to find the shortest path between the source node and the target node.

Step 1: For this, we have to first initialize the source node as a 0 and other nodes as ∞. Then we insert the pair <node, dist of node from original source node> into the dictionary. Our first pair will be <0, 0> because the distance from the source to the source itself is 0 as shown in the below graph and table.

Source Node Destination Node Dist from Source node Dictionary
0 0 0 [0, 0]
0 1 ∞
0 2 ∞
0 3 ∞
0 4 ∞
0 5 ∞

Step: 2 In the dictionary, there is only one pair <0, 0>. So, we take this as a current_source_node and relax the weight of the edges of all the adjacent nodes from the current_source_node (0).

current Source node Adjacent node Dist from Source (0) to adjacent node Update weight of egde or not
0 1 dist [ 1 ] = ∞ dist[ 1 ] > dist_between [ 0 – 1 ] + dist [ 0 ] i.e ∞ > 5 + 0 So, we are going to update the distance. Update dist => dist [ 1 ] = 5 and update the pair in the dict <1, 5>
0 2 dist [ 2 ] = ∞ dist [ 2 ] > dist_between [ 0 – 2 ] + distance [ 0 ] i.e ∞ > 1 + 0 So, we are going to update the distance. Update dist => dist [ 2 ] = 1 and update the pair in the dict <2 ,1>
0 3 dist [ 3 ] = ∞ dist [ 3 ] > dist_between [ 0 – 3 ] + dist [ 0 ] So, we are going to update the distance. i.e ∞ > 4 + 0 Update dist, i.e dist [ 3 ] = 4 and update the pair in the dict <3, 4>

Source Node Destination Node Dist from Source node Dictionary
0 0 0 [1, 5]
[2, 1]
[3, 4]
0 1 5
0 2 1
0 3 4
0 4 ∞
0 5 ∞

Step 3: Now, we remove the next pair from the dictionary for the current_source_node. But the condition is that, we have to choose minimum distance value node. So, we choose the <2, 1> from the dictionary and assigned as a current_source_node and relax the weight of the edges of all the adjacent nodes from the current_source_node (2).

current Source node Adjacent node Dist from Source (0) to adjacent node Update weight of egde or not
2 0 distance [ 0 ] = 0 dist [ 0 ] < dist_between [ 2 – 0 ] + dist [ 2 ] i.e 0 < 1 + 1 No weight update required. dist [ 1 ] > dist_between [ 2 – 1 ] + dist [ 2 ] i.e 5 > 3 + 1
2 1 distance [ 1 ] = 5 So, we are going to update the distance. Update dist ==>dist [ 1 ] = 4 and update the pair in the dict <1, 4> dist [ 3 ] > dist_between [ 2 – 3 ] + dist [ 2 ]i.e 4 > 2 + 1
2 3 distance [ 3 ] = 4 So, we are going to update the distance. Update dist => dist [ 3 ] = 3 and update the pair in the dict <3, 3> dist [ 4 ] > dist_between [ 2 – 4 ] + dist [ 2 ] i.e ∞ > 1 + 1
2 4 distance [ 4 ] = ∞ So, we are going to update the distance. Update dist => dist [ 4 ] = 2 update the pair in the dict <4, 2>

Source Node Destination Node Dist from Source node Dictionary
2 0 0 [1, 4]
[3, 3]
[4, 2]
2 1 4
2 2 1
2 3 3
2 4 2
2 5 ∞

Step 4: Now, we remove the next pair <4, 2> from the dictionary to choose current_source_node and relax the weight of the edges of all the adjacent nodes from the current_source_node (4).

current Source node Adjacent node Dist from Source (0) to adjacent node Update weight of egde or not
4 1 dist [ 1 ] = 4 dist [ 1 ] < dist_between [ 4 – 1 ] + dist [ 4 ] i.e 4 < 8 + 2 No weight updation required.
4 2 dist [ 2 ] = 1 dist [ 2 ] < dist_between [ 4 – 2 ] + dist [ 4 ] i.e 1 < 1 + 2 No weight updation required.
4 3 dist [ 3 ] = 3 dist [ 3 ] < dist_between [ 4 – 3 ] + dist [ 4 ] i.e 3 < 2 + 2 No weight updation required.
4 5 dist [ 5 ] = ∞ So, we are going to update the distance. Update dist => dist [ 5 ] = 5 update the pair in the dict <5, 5>

Source Node Destination Node Dist from Source node Dictionary
4 0 0 [1, 4]
[3, 3]
[5, 5]
4 1 4
4 2 1
4 3 3
4 4 2
4 5 5

Step 5: We remove the next pair <3, 3> from the dictionary to choose current_source_node and relax the weight of the edges of all the adjacent nodes from the current_source_node (3).

current Source node Adjacent node Dist from Source (0) to adjacent node Update weight of egde or not
3 0 dist [ 0 ] = 0 dist [ 0 ] < dist_between [ 3 – 0 ] + dist [ 3 ] i.e 0 < 4 + 3 No weight updation required.
3 2 dist [ 2 ] = 1 dist [ 2 ] < dist_between [ 3 – 2 ] + dist [ 3 ] i.e 1 < 2 + 3 No weight updation required.
3 4 dist [ 4 ] = 2 dist [ 4 ] < dist_between [ 3 – 4 ] + dist [ 3 ] i.e 2 < 2 + 3 No weight updation required.
3 5 dist [ 5 ] = 5 So, we are going to update the distance. Update dist =>dist [ 5 ] = 4 update the pair in the dict <5, 4>

Source Node Destination Node Dist from Source node Dictionary
3 0 0 [1, 4]
[5, 4]
3 1 4
3 2 1
3 3 3
3 4 2
3 5 4

Step 6: We remove the next pair <1, 4> from the dictionary to choose current_source_node and relax the weight of the edges of all the adjacent nodes from the current_source_node (1).

current Source node Adjacent node Dist from Source (0) to adjacent node Update weight of egde or not
1 0 dist [ 0 ] = 0 distance [ 0 ] < distance_between [ 1 – 0 ] + distance [ 1 ] i.e Since 0 < 5 + 4 No weight updation required.
1 2 dist [ 2 ] = 1 dist [ 2 ] < dist_between [ 1 – 2 ] + dist [ 1 ] i.e 1 < 3 + 4 No weight updation required.
1 4 dist [ 4 ] = 2 dist[ 4 ] < dist_between [ 1 – 4 ] + dist [ 1 ] i.e 2 < 8 + 4 No weight updation required.

Source Node Destination Node Dist from Source node Dictionary
1 0 0 [5, 4]
1 1 4
1 2 1
1 3 3
1 4 2
1 5 4

Step 7: Now, we remove the next pair <5, 4> from the dictionary to choose current_source_node and relax the weight of the edges of all the adjacent nodes from the current_source_node (5).

current Source node Adjacent node Dist from Source (0) to adjacent node Update weight of egde or not
5 3 dist [ 3 ] = 3 ddist [ 3 ] < dist_between [ 5 – 3 ] + dist [ 5 ] i.e 3 < 1 + 4 No weight updation required.
5 4 dist [ 4 ] = 2 dist [ 4 ] < dist_between [ 5 – 4 ] + dist [ 5 ] i.e 2 < 3 + 4 No weight updation required.

Now, the dictionary is null and no any pair left behind. So, our algorithm is now stopped. And we got all the shortest path from the main source node (S) to all others nodes as shown below:

Source Node Destination Node Dist from Source node Dictionary
0 0 0
0 1 4
0 2 1
0 3 3
0 4 2
0 5 4

Python code: Below is the implementation of the above algorithm.

1 # Dijkstra's Algorithm in Python
2 from collections import defaultdict
3
4 class Node_Dist:
5    def __init__(self, name, dist) :
6        self.name = name
7        self.dist = dist
8
9 class DijkstraAlgorithm:
10
11    def __init__(self, node_count) :
12        self.adjacentlist = defaultdict(list)
13        self.node_count = node_count
14
15    def Adjacent_nodelist(self, src, node_dist) :
16        self.adjacentlist[src].append(node_dist)
17
18    def Dijkstras_Shortest_Path(self, source_node) :
19        # Initialize the nodes with infinite value and source
20        # node with 0
21       dist = [999999999999] * self.node_count
22        dist[source_node] = 0
23
24        # we are creating a dict as said in the alogrithm with the
25        # value pair
26        dict_of_node_dist = {source_node: 0}
27
28        while dict_of_node_dist :
29
30            # Now, we are going to assing a pair  to a
31           # current_source_node but condition that dist value
32            # should be the minimum value
33            current_source_node = min(dict_of_node_dist,
34                                      key = lambda k: dict_of_node_dist[k])
35
36            # After assign that pair to the current_source_node,
37            # delete that item from the dict
38            del dict_of_node_dist[current_source_node]
39
40            for node_dist in self.adjacentlist[current_source_node] :
41                adjacentNode = node_dist.name
42                source_to_adjacentNode_dist = node_dist.dist
43
44                # We are doing here edge relaxation of the adjacent node
45                if dist[adjacentNode] > dist[current_source_node] + \
46                        source_to_adjacentNode_dist :
47                    dist[adjacentNode] = dist[current_source_node] + \
48                                         source_to_adjacentNode_dist
49                    dict_of_node_dist[adjacentNode] = dist[adjacentNode]
50
51        for i in range(self.node_count) :
52            print("Distance From Source Node ("+str(source_node)+")  => to "
53                        "Destination Node(" + str(i) + ")  => " + str(dist[i]))
54
55 def main() :
56
57    graph = DijkstraAlgorithm(6)
58    graph.Adjacent_nodelist(0, Node_Dist(1, 5))
59    graph.Adjacent_nodelist(0, Node_Dist(2, 1))
60    graph.Adjacent_nodelist(0, Node_Dist(3, 4))
61
62    graph.Adjacent_nodelist(1, Node_Dist(0, 5))
63    graph.Adjacent_nodelist(1, Node_Dist(2, 3))
64    graph.Adjacent_nodelist(1, Node_Dist(4, 8))
65
66    graph.Adjacent_nodelist(2, Node_Dist(0, 1))
67    graph.Adjacent_nodelist(2, Node_Dist(1, 3))
68    graph.Adjacent_nodelist(2, Node_Dist(3, 2))
69    graph.Adjacent_nodelist(2, Node_Dist(4, 1))
70
71    graph.Adjacent_nodelist(3, Node_Dist(0, 4))
72    graph.Adjacent_nodelist(3, Node_Dist(2, 2))
73    graph.Adjacent_nodelist(3, Node_Dist(4, 2))
74    graph.Adjacent_nodelist(3, Node_Dist(5, 1))
75
76    graph.Adjacent_nodelist(4, Node_Dist(1, 8))
77    graph.Adjacent_nodelist(4, Node_Dist(2, 1))
78    graph.Adjacent_nodelist(4, Node_Dist(3, 2))
79    graph.Adjacent_nodelist(4, Node_Dist(5, 3))
80
81    graph.Adjacent_nodelist(5, Node_Dist(3, 1))
82    graph.Adjacent_nodelist(5, Node_Dist(4, 3))
83
84    graph.Dijkstras_Shortest_Path(0)
85
86
87 if __name__ == "__main__" :
88   main()

Line 9 to 53: Explanation of this class is given below:

Line 9: We created a class the name DijkstraAlgorithm.

Line 11 to 16: We initialize the adjacentlist and node_count. The adjacentlist is a dict which we used to store the node and all their adjacent nodes, like Node 0: . This code if you print it will show the result like below:

defaultdict(<class 'list'>, {})
defaultdict(<class 'list'>, {0: [<__main__.Node_Dist object at 0x7f2b0a05abe0>]})

The above result shows that we are creating a dict that has all the details of a particular node and its adjacent nodes.

Line 21 to 22: We initialize all nodes with an infinity value and source nodes with 0 as per our algorithm.

Line 26: We initialize the dict_of_node_dist as per our algorithm, which is our first pair.

Line 28 to 50: We implement according to algorithm lines 4 to 8.

Line 57 to 83: We created an object of the class DijkstraAlgorithm and passed the number of nodes in the graph. Then we called the method Adjacent_nodelist using the object graph to make a dict of all the nodes with their adjacent nodes. The node will be the key and adjacent nodes and distance will be their values.

Line 83: We called the Dijkstras_Shortest_Path(0) method using the object graph.

Output: Python Dijkstra’s Algorithm.py

  1. Distance From Source Node (0) => to Destination Node(0) => 0
  2. Distance From Source Node (0) => to Destination Node(1) => 4
  3. Distance From Source Node (0) => to Destination Node(2) => 1
  4. Distance From Source Node (0) => to Destination Node(3) => 3
  5. Distance From Source Node (0) => to Destination Node(4) => 2
  6. Distance From Source Node (0) => to Destination Node(5) => 4

Conclusion

In this article, we have studied Dijkstra’s algorithm step by step. We have also studied the greedy approach idea. We do not include the details about the greedy approach because we will come back to this (greedy approach) topic later soon.

The code for this article is available at the Github link:
https://github.com/shekharpandey89/Dijkstra-s-algorithm

About the author

Shekhar Pandey

View all posts