# Python : Dijkstra's Shortest Path

Key points of Dijkstra’s single source shortest path algorithm are as below :

• Dijkstra’s algorithm finds the shortest path in a weighted graph containing only positive edge weights from a single source (node).

• It uses a priority-based dictionary or a queue to select a node / vertex nearest to the source that has not been edge relaxed.

Edge Relaxation in Dijkstra’s algorithm
Relaxing an edge in Dijkstra’s algorithm refers to updating the cost of all vertices connected to a vertex v, if those costs would be reduced by including vertex v in the path. Thus, if the source node is ( v ), then we check
If ( distance [ adjacent-node ] > length-of-path-to-adjacent-node-from-current-source ( v ) + distance [ current-source-node ( v ) ] ) {
distance [ adjacent-node ] = length-of-path-to-adjacent-node-from-current-source ( v ) + distance [ current-source-node ( v ) ]
}
Note :
a) The distance [ ] array stores the shortest distance of every node from the source-node.
b) Dijkstra’s algorithm begins by initializing distance [ original_source ] = 0 i.e the distance from the first (original) source node to itself is 0
and distance [ all_other_nodes ] = ∞.

• Since Dijkstra’s algorithm cannot handle negative edge weights, Bellman-Ford algorithm is used for finding the shortest path in a graph containing negative edge weights.

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 ] >

Data structures shown below 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.

Current
source node
node
from the original source ( 0 )
Edge relaxation
0 1 distance [ 1 ] = ∞ distance [ 1 ] > distance_between [ 0 - 1 ] + distance [ 0 ]
i.e Since ∞ > 5 + 0
Update 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 + 0
Update 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 + 0
Update 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 ).

Current
source node
node
from 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 + 1
Update 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 + 1
Update 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 + 1
Update 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 ).

Current
source node
node
from 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 + 2
Update 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 ).

Current
source node
node
from 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 + 3
Update 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 ).

Current
source node
node
from 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 ).

Current
source node
node
from 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 positive 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.node_count = node_count

def Dijkstras_Shortest_Path (self, source : int) :

# Initialize the distance of all the nodes from the source node to infinity
distance =  * 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]

# Edge relaxation

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>

# Node 1: <0,5> <2,3> <4,8>

# Node 2: <0,1> <1,3> <3,2> <4,1>

# Node 3: <0,4> <2,2> <4,2> <5,1>

# Node 4: <1,8> <2,1> <3,2> <5,3>

# Node 5: <3,1> <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
``````