Dijkstra's Shortest Path implementation in Python

Dijkstra’s Single Source Shortest Path

The gist of Dijkstra’s single source shortest path algorithm is as below :

  • Dijkstra’s algorithm finds the shortest path in a weighted graph containing only positive edge weights from a single source.
  • 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
    if ( distance [adjacent-node] > length-of-path-to-adjacent-node + distance [source-node] ) {
        distance [adjacent-node] = length-of-path-to-adjacent-node + distance [source-node];
    }
    Note :
    a) The distance [ ] array stores the shortest distance of every node from the source-node.
    b) Dijkstra’s algorithm begins by initializing distance [ source ] = 0 i.e the distance from 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.       source_node = DICTIONARY . get_key (node)_with_smallest_value (dist)
         Remove the key (source_node) from the DICTIONARY.
5.       For every adjacent_node to the source_node do
6.            If distance [adjacent_node] > length_to_adjacent_node_from_source + distance [source_node])
7.                 distance [adjacent_node] = length_to_adjacent_node_from_source + distance [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.

Adjacency list data structure for storing Dijkstras shortest path 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. Dijkstras shortest path step 1


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
Adjacent
node
Distance to the adjacent 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.
Dijkstras shortest path step 2

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
Adjacent
node
Distance to the adjacent 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.
Dijkstras shortest path step 3

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
Adjacent
node
Distance to the adjacent 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.
Dijkstras shortest path step 4

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
Adjacent
node
Distance to the adjacent 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.
Dijkstras shortest path step 5

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
Adjacent
node
Distance to the adjacent 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.
Dijkstras shortest path step 6

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
Adjacent
node
Distance to the adjacent 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.

Dijkstras shortest path step 7

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.


Python : Implementation of Dijkstra’s Shortest Path Algorithm In Python3

class Node_Distance :

    def __init__(self, name, dist) :
        self.name = name
        self.dist = dist

class Graph :

    def __init__(self, node_count) :
        self.adjlist = {}
        self.node_count = node_count

    def Add_Into_Adjlist(self, src, node_dist) :
        if src not in self.adjlist :
            self.adjlist[src] = []
        self.adjlist[src].append(node_dist)

    def Dijkstras_Shortest_Path(self, source) :

        # Initialize the distance of all the nodes from source 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
            source_node = min(dict_node_length, key = lambda k: dict_node_length[k])
            del dict_node_length[source_node]

            for node_dist in self.adjlist[source_node] :
                adjnode = node_dist.name
                length_to_adjnode = node_dist.dist

                # Edge relaxation
                if distance[adjnode] > distance[source_node] + length_to_adjnode :
                    distance[adjnode] = distance[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 of Dijkstra’s shortest path algorithm implemented in Python3

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

Copyright (c) 2020, Algotree.org.
All rights reserved.