The key points of Dijkstra’s single source shortest path algorithm is as below :
Algorithm : Dijkstra’s Shortest Path [Python 3]
1. Initialize the distance from the source node S to all other nodes as infinite (999999999999) and to itself as 0.
2. Insert the pair of < node, distance > for source i.e < S, 0 > in a DICTIONARY [Python3]
3. While the DICTIONARY is not empty do
4. current_source_node = DICTIONARY . get_key (node)_with_smallest_value (dist)
Remove the key (current_source_node) from the DICTIONARY.
5. For every adjacent_node to the current_source_node do
6. If ( distance [ adjacent_node ] > length_of_path_to_adjacent_node_from_current_source + distance [ current_source_node ] )
7. distance [ adjacent_node ] = length_of_path_to_adjacent_node_from_current_source + distance [ current_source_node ]
8. Update the DICTIONARY with the new pair < adjacent_node, distance [ adjacent_node ] >
Below data structures are used for storing the graph before running Dijkstra’s algorithm Adjacency List : List of pairs of adjacent nodes and their corresponding weights in the graph.
Dijkstra’s algorithm step-by-step This example of Dijkstra’s algorithm finds the shortest distance of all the nodes in the graph from the single / original source node 0.
Step 1 : Initialize the distance of the source node to itself as 0 and to all other nodes as ∞.
Insert the pair < node, distance_from_original_source > in the dictionary.
i.e Insert < 0, 0 > in the dictionary as the distance from the original source (0) to itself is 0.
Step 2 : Remove the pair < 0, 0 > from the dictionary and relax the edge going towards every adjacent node(s) from the original source node ( 0 ). The idea is to get the node with the shortest distance from the original source node.
Currentsource node | Adjacentnode | Distance to the adjacent nodefrom the original source ( 0 ) | Edge relaxation |
---|---|---|---|
0 | 1 | distance [ 1 ] = ∞ | distance [ 1 ] > distance_between [ 0 - 1 ] + distance [ 0 ]i.e Since ∞ > 5 + 0Update distance, i.e distance [ 1 ] = 5 i.e update pair_to < 1, 5 > in the dictionary. |
0 | 2 | distance [ 2 ] = ∞ | distance [ 2 ] > distance_between [ 0 - 2 ] + distance [ 0 ]i.e Since ∞ > 1 + 0Update distance, i.e distance [ 2 ] = 1 i.e update pair_to < 2, 1 > in the dictionary. |
0 | 3 | distance [ 3 ] = ∞ | distance [ 3 ] > distance_between [ 0 - 3 ] + distance [ 0 ]i.e Since ∞ > 4 + 0Update distance, i.e distance [ 3 ] = 4 i.e update pair_to < 3, 4 > in the dictionary. |
Step 3 : Remove the pair < 2, 1 > from the dictionary and relax the edge going towards every adjacent node(s) from the current source ( 2 ).
Currentsource node | Adjacentnode | Distance to the adjacent nodefrom the original source ( 0 ) | Edge relaxation |
---|---|---|---|
2 | 0 | distance [ 0 ] = 0 | distance [ 0 ] < distance_between [ 2 - 0 ] + distance [ 2 ]i.e Since 0 < 1 + 1 No edge relaxation needed. |
2 | 1 | distance [ 1 ] = 5 | distance [ 1 ] > distance_between [ 2 - 1 ] + distance [ 2 ]i.e Since 5 > 3 + 1Update distance, i.e distance [ 1 ] = 4 and update pair_to < 1, 4 > in the dictionary. |
2 | 3 | distance [ 3 ] = 4 | distance [ 3 ] > distance_between [ 2 - 3 ] + distance [ 2 ]i.e Since 4 > 2 + 1Update distance, i.e distance [ 3 ] = 3 and update pair_to < 3, 3 > in the dictionary. |
2 | 4 | distance [ 4 ] = ∞ | distance [ 4 ] > distance_between [ 2 - 4 ] + distance [ 2 ]i.e Since ∞ > 1 + 1Update distance, i.e distance [ 4 ] = 2 and update pair_to < 4, 2 > in the dictionary. |
Step 4 : Remove the pair < 4, 2 > from the dictionary and relax the edge going towards every adjacent node(s) from the current source ( 4 ).
Currentsource node | Adjacentnode | Distance to the adjacent nodefrom the original source ( 0 ) | Edge relaxation |
---|---|---|---|
4 | 1 | distance [ 1 ] = 4 | distance [ 1 ] < distance_between [ 4 - 1 ] + distance [ 4 ]i.e Since 4 < 8 + 2 No edge relaxation needed. |
4 | 2 | distance [ 2 ] = 1 | distance [ 2 ] < distance_between [ 4 - 2 ] + distance [ 4 ]i.e Since 1 < 1 + 2 No edge relaxation needed. |
4 | 3 | distance [ 3 ] = 3 | distance [ 3 ] < distance_between [ 4 - 3 ] + distance [ 4 ]i.e Since 3 < 2 + 2 No edge relaxation needed. |
4 | 5 | distance [ 5 ] = ∞ | distance [ 5 ] > distance_between [ 4 - 5 ] + distance [ 4 ]i.e Since ∞ > 3 + 2Update distance, i.e distance [ 5 ] = 5 and update pair_to < 5, 5 > in the dictionary. |
Step 5 : Remove the pair < 3, 3 > from the dictionary and relax the edge going towards every adjacent node(s) from the current source ( 3 ).
Currentsource node | Adjacentnode | Distance to the adjacent nodefrom the original source ( 0 ) | Edge relaxation |
---|---|---|---|
3 | 0 | distance [ 0 ] = 0 | distance [ 0 ] < distance_between [ 3 - 0 ] + distance [ 3 ]i.e Since 0 < 4 + 3 No edge relaxation needed. |
3 | 2 | distance [ 2 ] = 1 | distance [ 2 ] < distance_between [ 3 - 2 ] + distance [ 3 ]i.e Since 1 < 2 + 3 No edge relaxation needed. |
3 | 4 | distance [ 4 ] = 2 | distance [ 4 ] < distance_between [ 3 - 4 ] + distance [ 3 ]i.e Since 2 < 2 + 3 No edge relaxation needed. |
3 | 5 | distance [ 5 ] = 5 | distance [ 5 ] > distance_between [ 3 - 5 ] + distance [ 3 ]i.e Since 5 > 1 + 3Update distance, i.e distance [ 5 ] = 4 and update pair_to < 5, 4 > in the dictionary. |
Step 6 : Remove the pair < 1, 4 > from the dictionary and relax the edge going towards every adjacent node(s) from the current source ( 1 ).
Currentsource node | Adjacentnode | Distance to the adjacent nodefrom the original source ( 0 ) | Edge relaxation |
---|---|---|---|
1 | 0 | distance [ 0 ] = 0 | distance [ 0 ] < distance_between [ 1 - 0 ] + distance [ 1 ]i.e Since 0 < 5 + 4 No edge relaxation needed. |
1 | 2 | distance [ 2 ] = 1 | distance [ 2 ] < distance_between [ 1 - 2 ] + distance [ 1 ]i.e Since 1 < 3 + 4 No edge relaxation needed. |
1 | 4 | distance [ 4 ] = 2 | distance [ 4 ] < distance_between [ 1 - 4 ] + distance [ 1 ]i.e Since 2 < 8 + 4 No edge relaxation needed. |
Step 7 : Remove the pair < 5, 4 > from the dictionary and relax the edge going towards every adjacent node(s) from the current source ( 5 ).
Currentsource node | Adjacentnode | Distance to the adjacent nodefrom the original source ( 0 ) | Edge relaxation |
---|---|---|---|
5 | 3 | distance [ 3 ] = 3 | distance [ 3 ] < distance_between [ 5 - 3 ] + distance [ 5 ]i.e Since 3 < 1 + 4 No edge relaxation needed. |
5 | 4 | distance [ 4 ] = 2 | distance [ 4 ] < distance_between [ 5 - 4 ] + distance [ 5 ]i.e Since 2 < 3 + 4 No edge relaxation needed. |
The algorithm terminates here as the dictionary is empty and we have calculated the shortest path to all the nodes from the original source 0 as shown below.
Data structure used for running Dijkstra’s shortest path : Dictionary storing the nodes and their length from the source.
Graph type: Designed for weighted (directed / un-directed) graph containing positve edge weights.
Time complexity of Dijkstra’s algorithm : O ( ( E + V ) Log ( V ) ) for an adjacency list implementation of a graph. V is the
number of vertices and E is the number of edges in a graph.
from collections import defaultdict
class Node_Distance :
def __init__(self, name : int, dist : int) :
self.name = name
self.dist = dist
class Graph :
def __init__ (self, node_count : int) :
# Store the adjacency list as a dictionary
# The default dictionary would create an empty list as a default (value)
# for the nonexistent keys.
self.adjlist = defaultdict(list)
self.node_count = node_count
def Add_Into_Adjlist (self, src : int, node_dist : Node_Distance(int,int)) :
self.adjlist[src].append(node_dist)
def Dijkstras_Shortest_Path (self, source : int) :
# Initialize the distance of all the nodes from the source node to infinity
distance = [999999999999] * self.node_count
# Distance of source node to itself is 0
distance[source] = 0
# Create a dictionary of { node, distance_from_source }
dict_node_length = {source: 0}
while dict_node_length :
# Get the key for the smallest value in the dictionary
# i.e Get the node with the shortest distance from the source
current_source_node = min(dict_node_length, key = lambda k: dict_node_length[k])
del dict_node_length[current_source_node]
for node_dist in self.adjlist[current_source_node] :
adjnode = node_dist.name
length_to_adjnode = node_dist.dist
# Edge relaxation
if distance[adjnode] > distance[current_source_node] + length_to_adjnode :
distance[adjnode] = distance[current_source_node] + length_to_adjnode
dict_node_length[adjnode] = distance[adjnode]
for i in range(self.node_count) :
print("Source Node ("+str(source)+") -> Destination Node(" + str(i) + ") : " + str(distance[i]))
def main() :
g = Graph(6)
# Node 0: <1,5> <2,1> <3,4>
g.Add_Into_Adjlist(0, Node_Distance(1, 5))
g.Add_Into_Adjlist(0, Node_Distance(2, 1))
g.Add_Into_Adjlist(0, Node_Distance(3, 4))
# Node 1: <0,5> <2,3> <4,8>
g.Add_Into_Adjlist(1, Node_Distance(0, 5))
g.Add_Into_Adjlist(1, Node_Distance(2, 3))
g.Add_Into_Adjlist(1, Node_Distance(4, 8))
# Node 2: <0,1> <1,3> <3,2> <4,1>
g.Add_Into_Adjlist(2, Node_Distance(0, 1))
g.Add_Into_Adjlist(2, Node_Distance(1, 3))
g.Add_Into_Adjlist(2, Node_Distance(3, 2))
g.Add_Into_Adjlist(2, Node_Distance(4, 1))
# Node 3: <0,4> <2,2> <4,2> <5,1>
g.Add_Into_Adjlist(3, Node_Distance(0, 4))
g.Add_Into_Adjlist(3, Node_Distance(2, 2))
g.Add_Into_Adjlist(3, Node_Distance(4, 2))
g.Add_Into_Adjlist(3, Node_Distance(5, 1))
# Node 4: <1,8> <2,1> <3,2> <5,3>
g.Add_Into_Adjlist(4, Node_Distance(1, 8))
g.Add_Into_Adjlist(4, Node_Distance(2, 1))
g.Add_Into_Adjlist(4, Node_Distance(3, 2))
g.Add_Into_Adjlist(4, Node_Distance(5, 3))
# Node 5: <3,1> <4,3>
g.Add_Into_Adjlist(5, Node_Distance(3, 1))
g.Add_Into_Adjlist(5, Node_Distance(4, 3))
g.Dijkstras_Shortest_Path(0)
print("\n")
g.Dijkstras_Shortest_Path(5)
if __name__ == "__main__" :
main()
Output
Source Node (0) -> Destination Node(0) : 0
Source Node (0) -> Destination Node(1) : 4
Source Node (0) -> Destination Node(2) : 1
Source Node (0) -> Destination Node(3) : 3
Source Node (0) -> Destination Node(4) : 2
Source Node (0) -> Destination Node(5) : 4
Source Node (5) -> Destination Node(0) : 4
Source Node (5) -> Destination Node(1) : 6
Source Node (5) -> Destination Node(2) : 3
Source Node (5) -> Destination Node(3) : 1
Source Node (5) -> Destination Node(4) : 3
Source Node (5) -> Destination Node(5) : 0