Dijkstra's Algorithm Explained: Implementing with Python for Optimal Pathfinding - AskPython (2024)

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.

Dijkstra's Algorithm Explained: Implementing with Python for Optimal Pathfinding - AskPython (1)

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.

Dijkstra's Algorithm Explained: Implementing with Python for Optimal Pathfinding - AskPython (2)

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.

Dijkstra's Algorithm Explained: Implementing with Python for Optimal Pathfinding - AskPython (3)

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

Dijkstra's Algorithm Explained: Implementing with Python for Optimal Pathfinding - AskPython (2024)
Top Articles
Latest Posts
Recommended Articles
Article information

Author: Duncan Muller

Last Updated:

Views: 5717

Rating: 4.9 / 5 (79 voted)

Reviews: 86% of readers found this page helpful

Author information

Name: Duncan Muller

Birthday: 1997-01-13

Address: Apt. 505 914 Phillip Crossroad, O'Konborough, NV 62411

Phone: +8555305800947

Job: Construction Agent

Hobby: Shopping, Table tennis, Snowboarding, Rafting, Motor sports, Homebrewing, Taxidermy

Introduction: My name is Duncan Muller, I am a enchanting, good, gentle, modern, tasty, nice, elegant person who loves writing and wants to share my knowledge and understanding with you.