Dijkstra’s Algorithm in Python

The single-source shortest path problem is about finding the paths between a given vertex(called the source) to all the other vertices(called the destination) in a graph such that the total distance between them is minimum.

Dijkstra’s algorithm is an algorithm for finding the shortest path between any two nodes of a given graph. While traversing the shortest path between two nodes, it is not necessary that every node will be visited.

Dijkstra’s algorithm can be used to solve the SSSP problem for weighted graphs. In the above example, the shortest path between the vertices V5 and V3 is numerically weighted 8(V5 -> V4 -> V3).

Dijkstra’s Algorithm finds use in various real-life applications:

• Digital Mapping Services
• Social Networking Applications
• Telephone Network
• IP Routing to find the shortest path

Creation of Graph

To implement the Graph data structure, we first initialize the “Graph” class. Then, we overwrite the __init__ function and create another function to add weighted edges between the newly added nodes.

#Initializing the Graph Class
class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = defaultdict(list)
        self.distances = {}
    
    def addNode(self,value):
        self.nodes.add(value)
    
    def addEdge(self, fromNode, toNode, distance):
        self.edges[fromNode].append(toNode)
        self.distances[(fromNode, toNode)] = distance

Implementation of Dijkstra’s Algorithm to solve SSSP Problem

To implement Dijkstra’s algorithm in python, we create the dijkstra method which takes two parameters – the graph under observation and the initial node which will be the source point for our algorithm.

Dijkstra’s algorithm is based on the following steps:

• We will receive a weighted graph and an initial node.
• Start with the initial node. Check the adjacent nodes.
• Find the node with the minimum edge value.
• Repeat this process until the destination node is visited.
• At the end of the function, we return the shortest path weight for each node and the path as well.

#Implementing Dijkstra's Algorithm
def dijkstra(graph, initial):
    visited = {initial : 0}
    path = defaultdict(list)

    nodes = set(graph.nodes)

    while nodes:
        minNode = None
        for node in nodes:
            if node in visited:
                if minNode is None:
                    minNode = node
                elif visited[node] < visited[minNode]:
                    minNode = node
        if minNode is None:
            break

        nodes.remove(minNode)
        currentWeight = visited[minNode]

        for edge in graph.edges[minNode]:
            weight = currentWeight + graph.distances[(minNode, edge)]
            if edge not in visited or weight < visited[edge]:
                visited[edge] = weight
                path[edge].append(minNode)
    
    return visited, path

customGraph = Graph()
customGraph.addNode("A")
customGraph.addNode("B")
customGraph.addNode("C")
customGraph.addNode("D")
customGraph.addNode("E")
customGraph.addNode("F")
customGraph.addNode("G")
customGraph.addEdge("A", "B", 2)
customGraph.addEdge("A", "C", 5)
customGraph.addEdge("B", "C", 6)
customGraph.addEdge("B", "D", 1)
customGraph.addEdge("B", "E", 3)
customGraph.addEdge("C", "F", 8)
customGraph.addEdge("D", "E", 4)
customGraph.addEdge("E", "G", 9)
customGraph.addEdge("F", "G", 7)

print(dijkstra(customGraph, "A"))

#Output
({'A': 0, 'B': 2, 'C': 5, 'D': 3, 'E': 5, 'G': 14, 'F': 13},
 defaultdict(<class 'list'>, 
{'B': ['A'], 'C': ['A'], 'D': ['B'], 'E': ['B'], 'G': ['E'], 'F': ['C']}))

Time and Space Complexity

The time complexity for Dijkstra’s algorithm is O(V^2) where “V” is the number of vertices of the graph. This is due to the fact that we have used two loops nested together and each of them iterates over all the nodes.

The space complexity is O(E) where “E” is the number of edges of the graph because we are appending path with the edges.