Dijkstra's Algorithm a graph with non negative edge weights Python

Dijkstra's Algorithm: Implement Dijkstra's algorithm to find the shortest path in a graph with non-negative edge weights Python Program?

Dijkstra's algorithm is a classic algorithm for finding the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights. It uses a priority queue to efficiently get the vertex with the smallest tentative distance.

Steps to Implement Dijkstra's Algorithm

1. Initialize:

   • Set the distance to the source vertex as 0 and all other distances to infinity.
   • Use a priority queue (min-heap) to store vertices and their current shortest distances.

2. Process Vertices:

   • Extract the vertex with the minimum distance from the priority queue.
   • Update the distances to its adjacent vertices if a shorter path is found through this vertex.
   • Push the updated distances into the priority queue.

3. Repeat:

   • Continue until the priority queue is empty.

Python Implementation

Here’s a Python implementation using a priority queue provided by the heapq module:

import heapq

def dijkstra(graph, start):

    # Initialize distances with infinity and set the distance to the start node as 0

    distances = {vertex: float('infinity') for vertex in graph}

    distances[start] = 0

    

    # Priority queue to store (distance, vertex) tuples

    priority_queue = [(0, start)]

    

    while priority_queue:

        current_distance, u = heapq.heappop(priority_queue)

        

        # If a node's distance is updated after it's popped, skip processing

        if current_distance > distances[u]:

            continue

        

        # Check the distance to each neighbor

        for neighbor, weight in graph[u].items():

            distance = current_distance + weight

            

            # Only consider this new path if it's shorter

            if distance < distances[neighbor]:

                distances[neighbor] = distance

                heapq.heappush(priority_queue, (distance, neighbor))

    

    return distances

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

shortest_paths = dijkstra(graph, start_node)

print(shortest_paths)  # Output: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

Explanation

1. Initialization:

   • distances: A dictionary to store the shortest distance from the start vertex to each vertex.
   • priority_queue: A min-heap that stores vertices along with their current shortest distances.

2. Processing the Priority Queue:

   • Extract the vertex with the smallest distance from the priority queue.
   • For each neighbor of this vertex, calculate the distance through the current vertex.
   • If this new distance is shorter, update the shortest distance and add the neighbor to the priority queue with the updated distance.

3. Completion:

   • The distances dictionary will have the shortest path from the start node to every other node when the algorithm completes.

Complexity

• Time Complexity: $O((V + E) \log V)$, where $V$ is the number of vertices and $E$ is the number of edges. This is due to the priority queue operations.
• Space Complexity: $O(V)$ for storing distances and the priority queue.

Dijkstra's algorithm is efficient for graphs with non-negative weights and is widely used in various applications like routing and network optimization.