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
Recommended: Maximizing Cost Savings Through Offshore Development: A Comprehensive Guide
Recommended: Connected Health: Exploring IoT Solutions for Healthcare Transformation
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 networkximport networkx as nximport heapqimport 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 usagegraph = { '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 graphG = nx.DiGraph(graph)# Draw the graphpos = 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 labelsedge_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 labelsnode_labels = {node: f"{node}\n({shortest_distances[node]})" for node in G.nodes()}nx.draw_networkx_labels(G, pos, labels=node_labels)# Show the plotplt.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.
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 heapqimport networkx as nximport matplotlib.pyplot as pltdef 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 usagegraph = { '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 graphG = nx.DiGraph()# Add nodes and edges to the graphfor city, neighbors in graph.items(): for neighbor, distance in neighbors.items(): G.add_edge(city, neighbor, weight=distance)# Draw the graphpos = 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 pathshortest_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 plotplt.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.
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?
Recommended: Random Search in Machine Learning: Hyperparameter Tuning Technique
Recommended: Levenshtein Distance in Python: Troubleshooting Installation Errors on Windows
