Develop a Program to Find the Shortest Path in a Graph Using Dijkstra’s Algorithm in Python

Dijkstra’s algorithm is a popular algorithm used to find the shortest path from a starting node to all other nodes in a weighted graph. Below is a Python implementation of Dijkstra’s algorithm.

Implementation of Dijkstra’s Algorithm in Python

import heapq

def dijkstra(graph, start):
    # Priority queue to store (distance, node) pairs
    priority_queue = [(0, start)]
    # Dictionary to store the shortest path to each node
    shortest_paths = {start: 0}
    # Dictionary to track the best path to each node
    previous_nodes = {start: None}

    while priority_queue:
        # Extract the node with the smallest distance
        current_distance, current_node = heapq.heappop(priority_queue)

        # Explore neighbors of the current node
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            # Only consider this new path if it's shorter
            if neighbor not in shortest_paths or distance < shortest_paths[neighbor]:
                shortest_paths[neighbor] = distance
                previous_nodes[neighbor] = current_node
                heapq.heappush(priority_queue, (distance, neighbor))

    return shortest_paths, previous_nodes

def reconstruct_path(previous_nodes, start, end):
    path = []
    current_node = end

    while current_node is not None:
        path.append(current_node)
        current_node = previous_nodes[current_node]

    path.reverse()
    return path if path[0] == start else []

# Example usage:
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

start_node = 'A'
end_node = 'D'
shortest_paths, previous_nodes = dijkstra(graph, start_node)
path = reconstruct_path(previous_nodes, start_node, end_node)

print(f"Shortest path from {start_node} to {end_node}: {path}")
print(f"Shortest distance from {start_node} to {end_node}: {shortest_paths[end_node]}")

Explanation of the Code:

1. Graph Representation:
   • The graph is represented as an adjacency list using a dictionary of dictionaries. Each key represents a node, and its value is another dictionary where the keys are the neighboring nodes and the values are the weights of the edges.
2. Dijkstra’s Algorithm (dijkstra function):
   • Priority Queue: A priority queue (implemented using heapq) is used to always expand the node with the smallest known distance.
   • Shortest Paths: A dictionary shortest_paths keeps track of the minimum distance from the start node to each node.
   • Previous Nodes: A dictionary previous_nodes is used to reconstruct the shortest path by keeping track of the best predecessor for each node.
   • Main Loop: The algorithm repeatedly extracts the closest unvisited node and updates the distances to its neighbors. If a shorter path to a neighbor is found, the neighbor’s distance is updated, and it’s added to the priority queue.
3. Reconstruct Path (reconstruct_path function):
   • This function takes the previous_nodes dictionary and reconstructs the shortest path from the start node to the end node by backtracking from the end node to the start node.

Example Usage:

• Graph: The example graph has nodes ‘A’, ‘B’, ‘C’, and ‘D’ with various weighted edges connecting them.
• Output:
• The program will find the shortest path from node ‘A’ to node ‘D’ and print the path and the distance.

Shortest path from A to D: [‘A’, ‘B’, ‘C’, ‘D’]

Shortest distance from A to D: 4

Customization:

• You can modify the graph dictionary to test the algorithm with different graphs.
• The start_node and end_node variables can be adjusted to find paths between different nodes.

This implementation of Dijkstra’s algorithm efficiently finds the shortest path in a weighted graph and can be adapted for more complex applications.