Dijkstra’s algorithm Python program

Dijkstra’s Algorithm Using Python

Introduction

Dijkstra’s algorithm finds the shortest path from a starting node to all other nodes in a weighted graph. In this tutorial, we’ll break down the implementation of this algorithm into smaller, easy-to-understand code blocks.

1. Importing the Required Module

First, we need to import the heapq module, which is used to maintain a priority queue for efficiently retrieving the node with the smallest distance.

import heapq

heapq: This module provides an implementation of the min-heap data structure, which is crucial for efficiently finding the shortest path in Dijkstra’s algorithm.

2. Defining the Graph Class

We start by defining a Graph class. This class will handle the graph’s vertices and edges, and will include methods for adding vertices and edges, displaying the graph, and finding the shortest path.

class Graph:
    def __init__(self):
        self.graph = {}  # Dictionary to store the graph

__init__: This is the constructor method for the Graph class. It initializes an empty dictionary, self.graph, which will be used to store the graph’s vertices and edges.

3. Adding Vertices

Next, we define a method to add vertices to the graph.

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = {}  # Initialize with an empty dictionary for edges

add_vertex: This method takes a vertex as input. It adds the vertex to the self.graph dictionary with an empty dictionary as its value, which will later hold its edges and corresponding weights. The if statement ensures that we only add a vertex if it’s not already present.

4. Adding Edges

Now, let’s define the method for adding edges between vertices.

    def add_edge(self, vertex1, vertex2, weight):
        if vertex1 in self.graph and vertex2 in self.graph:
            self.graph[vertex1][vertex2] = weight
            self.graph[vertex2][vertex1] = weight  # For undirected graph
        else:
            print(f"One or both vertices not found.")

add_edge: This method takes two vertices and a weight as inputs. It adds an edge between vertex1 and vertex2 with the specified weight. Since the graph is undirected, we add the edge in both directions. The if statement checks that both vertices exist in the graph.

5. Displaying the Graph

Here’s how we display the graph’s vertices and edges.

    def display(self):
        for vertex, edges in self.graph.items():
            print(f"{vertex}: {', '.join(f'{neigh} ({wt})' for neigh, wt in edges.items())}")

display: This method iterates over each vertex and its edges in the self.graph dictionary. It prints the vertex and its neighbors along with the weight of the edges. The join method formats the output to make it more readable.

6. Implementing Dijkstra’s Algorithm

Now, let’s add the method to find the shortest path using Dijkstra’s algorithm.

    def shortest_path(self, start, end):
        # Priority queue for Dijkstra's algorithm
        queue = [(0, start)]
        distances = {vertex: float('inf') for vertex in self.graph}
        distances[start] = 0
        previous_nodes = {vertex: None for vertex in self.graph}

        while queue:
            current_distance, current_vertex = heapq.heappop(queue)

            if current_distance > distances[current_vertex]:
                continue

            for neighbor, weight in self.graph[current_vertex].items():
                distance = current_distance + weight

                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    previous_nodes[neighbor] = current_vertex
                    heapq.heappush(queue, (distance, neighbor))

        # Reconstruct the shortest path
        path = []
        while end is not None:
            path.append(end)
            end = previous_nodes[end]

        return path[::-1], distances[path[0]]

shortest_path: This method finds the shortest path from the start vertex to the end vertex using Dijkstra’s algorithm.
Priority Queue Initialization: The queue starts with a tuple (0, start), where 0 is the initial distance and start is the starting vertex.
Distance Initialization: distances dictionary keeps track of the shortest known distance to each vertex. Initially, all distances are set to infinity except for the start vertex, which is set to 0.
Previous Nodes: previous_nodes keeps track of the best previous vertex for each vertex to reconstruct the path.
Processing Queue: The algorithm extracts the vertex with the smallest distance from the priority queue, updates the distances to its neighbors, and pushes these neighbors into the queue if a shorter path is found.
Path Reconstruction: After processing, the path is reconstructed by tracing back from the end vertex to the start vertex using previous_nodes.

7. Example Usage

Finally, here’s how to use the Graph class to create a graph, add vertices and edges, and find the shortest path.

# Example usage
if __name__ == "__main__":
    # Create a graph instance
    g = Graph()

    # Adding vertices
    g.add_vertex('A')
    g.add_vertex('B')
    g.add_vertex('C')
    g.add_vertex('D')

    # Adding edges with weights
    g.add_edge('A', 'B', 1)
    g.add_edge('A', 'C', 4)
    g.add_edge('B', 'C', 2)
    g.add_edge('C', 'D', 1)

    # Display the graph
    print("Graph:")
    g.display()

    # Find shortest path from A to D
    path, distance = g.shortest_path('A', 'D')
    print(f"\nShortest path from A to D: {' -> '.join(path)} with distance {distance}")

Creating the Graph: An instance of the Graph class is created.
Adding Vertices and Edges: Vertices and weighted edges are added to the graph.
Displaying the Graph: The graph’s structure is printed.
Finding the Shortest Path: The shortest path from vertex A to vertex D is calculated and displayed.

Conclusion

By breaking down Dijkstra’s algorithm into these manageable code blocks, you can see how each part contributes to finding the shortest path in a graph. This implementation provides a clear and practical way to understand and apply Dijkstra’s algorithm in Python.