Dijkstra's Algorithm Explained: Implementing with Python for Optimal Pathfinding

Connectivity between cities poses many issues to the supply chain. There are no train transportation facilities in the towns of Himachal Pradesh, Jammu, and Kashmir, and thus, it is essential to decrease transportation and other costs.

Dijkstra’s algorithm is one such method for finding the minimum distance between two cities or nodes. In this article, we will discuss this algorithm and understand its Python implementation.

Dijkstra’s algorithm is an efficient technique for finding the shortest path between nodes in a graph. It works by iteratively determining the minimal distance from a starting node to all other nodes, using a priority queue to explore the most promising paths first. This Python tutorial explains how to implement Dijkstra’s algorithm to compute shortest paths effectively

Understanding Dijkstra’s Algorithm

This algorithm is very famous among people studying computer science. It is used to measure the shortest distance between the nodes with weights being attached to them. It is also an iterative process with random distances assumed between each pair of nodes. Let us understand it with a code in the next section.

Let us now look at its implementation in Python programming language.

Python Code Implementation

Let us understand this phenomenon with Python code.

!pip install networkx

import networkx as nx
import heapq
import matplotlib.pyplot as plt

These are the necessary libraries required to code our algorithms, networkx is used to plot the graphs, heapq is used to make queues, and matplotlib for visualization.

def dijkstra(graph, start):
    # Initialize distances dictionary
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # Initialize priority queue
    pq = [(0, start)]

The above function is used to plot the shortest distance between the two nodes where all the nodes have some weight. We also initialize a queue which will be used to assign particular importance to different nodes.

while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        # If we already found a shorter path, skip
        if current_distance > distances[current_node]:
            continue
        
        # Explore neighbors
        for neighbor, weight_dict in graph[current_node].items():
            weight = weight_dict['weight']
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

We now introduce a loop where we find out the minimum distance between two nodes as defined by the heapq which gives the priority order of the nodes. Accordingly, distance is found between each node and based on the distance, priority is assigned to each of them based on which further weightage of the paths is decided.

# Example usage
graph = {
    'A': {'B': {'weight': 2}, 'C': {'weight': 1}},
    'B': {'A': {'weight': 2}, 'C': {'weight': 4}, 'D': {'weight': 3}},
    'C': {'A': {'weight': 1}, 'B': {'weight': 4}, 'D': {'weight': 5}},
    'D': {'B': {'weight': 3}, 'C': {'weight': 5}}
}
start_node = 'A'
shortest_distances = dijkstra(graph, start_node)

# Create a directed graph
G = nx.DiGraph(graph)

# Draw the graph
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_size=1500, node_color="skyblue", font_size=15, font_weight="bold")

# Draw edge labels
edge_labels = {(u, v): d['weight'] for u, v, d in G.edges(data=True)}
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_color='red')

# Draw node labels
node_labels = {node: f"{node}\n({shortest_distances[node]})" for node in G.nodes()}
nx.draw_networkx_labels(G, pos, labels=node_labels)

# Show the plot
plt.title("Shortest Path Graph")
plt.axis("off")
plt.show()

Now, in the example, we have a dictionary with weights and nodes predefined. We set the starting node as ‘A’ and then Dijkstra’s algorithm is applied with the results being stored in a different dictionary. We then visualize the above plot using different libraries of the Python programming language.

We can see that this is an iterative code. Let us look at its output.

Dijkstras Algorithm Output — ***Visualizing Algorithm Results***

Case Study: Shortest Path in Indian Cities

Let us understand this concept with a simple case study. We have some Indian cities like Mumbai, Nagpur, etc. given in the code below, for which we want to minimize the distance. We need to find the best route possible from Nagpur.

import heapq
import networkx as nx
import matplotlib.pyplot as plt

def dijkstra(graph, start, end):
    # Initialize distances dictionary
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # Initialize priority queue
    pq = [(0, start)]
    
    # Initialize previous node dictionary to store shortest path
    previous = {}
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        # If we already found a shorter path to the current node, skip
        if current_distance > distances[current_node]:
            continue
        
        # Stop if we reached the destination
        if current_node == end:
            break
        
        # Explore neighbors
        for neighbor, distance in graph[current_node].items():
            new_distance = current_distance + distance
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                heapq.heappush(pq, (new_distance, neighbor))
                previous[neighbor] = current_node
    
    # Reconstruct the shortest path
    path = []
    node = end
    while node != start:
        path.append(node)
        node = previous[node]
    path.append(start)
    path.reverse()
    
    return distances[end], path

# Example usage
graph = {
    'Mumbai': {'Pune': 150, 'Nagpur': 700, 'Ahmedabad': 500},
    'Pune': {'Mumbai': 150, 'Nagpur': 800, 'Bangalore': 800},
    'Nagpur': {'Mumbai': 700, 'Pune': 800, 'Delhi': 1000},
    'Ahmedabad': {'Mumbai': 500, 'Bangalore': 1000},
    'Bangalore': {'Pune': 800, 'Ahmedabad': 1000, 'Delhi': 2000},
    'Delhi': {'Nagpur': 1000, 'Bangalore': 2000}
}

start_city = 'Mumbai'
destination_city = 'Delhi'
shortest_distance, shortest_path = dijkstra(graph, start_city, destination_city)
print(f"The shortest distance from {start_city} to {destination_city} is {shortest_distance} km")
print("Shortest path:", shortest_path)

# Create a directed graph
G = nx.DiGraph()

# Add nodes and edges to the graph
for city, neighbors in graph.items():
    for neighbor, distance in neighbors.items():
        G.add_edge(city, neighbor, weight=distance)

# Draw the graph
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_size=1500, node_color="skyblue", font_size=10, font_weight="bold")

# Highlight shortest path
shortest_path_edges = [(shortest_path[i], shortest_path[i + 1]) for i in range(len(shortest_path) - 1)]
nx.draw_networkx_edges(G, pos, edgelist=shortest_path_edges, edge_color='red', width=2)

# Show the plot
plt.title("Shortest Path in Indian Road Network")
plt.axis("off")
plt.show()

Let us look at the output for the same. Essentially, we have highlighted the shortest routes with red as displayed in the output. The above code is more or less similar to the code discussed in the previous section.

***Dijkstras Algorithm Case Study Output***

Conclusion

You’ve now mastered Dijkstra’s algorithm and its practical application in Python. Whether optimizing routes or solving complex network issues, this algorithm stands as a cornerstone in the field of computational theory and operations research. How might these principles be applied to optimize daily logistics in your community?