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

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

## 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*