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.

Dijkstras_ShortestPath_DataStructure

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_Python

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_Python

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_Python

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_Python

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_Python

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_Python

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_Python

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

Copyright (c) 2019-2024, Algotree.org.
All rights reserved.