Dijkstra's algorithm

[Invincible1602]

Hey @DhanushNehru,

I want to implement the Dijkstra's Algorithm in Python. Dijkstra's algorithm is a greedy algorithm that finds the shortest paths in a graph with non-negative edge weights by following these steps:

• Initialize the distance to the source vertex as 0 and to all other vertices as infinity.
• Use a priority queue (min-heap) to select the vertex with the smallest distance that has not yet been processed.
• For the selected vertex, check all of its adjacent vertices. For each adjacent vertex, calculate the tentative distance from the source vertex through the selected vertex. If this tentative distance is smaller than the currently known distance, update the shortest distance. Repeat this process until all vertices have been processed.

Input:

• A connected, weighted graph represented as an adjacency list, where the keys represent vertices and the values represent dictionaries of neighboring vertices with their edge weights.
• The source vertex from which the shortest paths are to be calculated.

Output:

• A dictionary representing the shortest distances from the source vertex to all other vertices in the graph.

Please assign me the issue and hacktoberfest label.

[mukprabhakar]

Python implementation of Dijkstra's Algorithm using a priority queue (min-heap) to find the shortest path in a graph with non-negative edge weights: import heapq

def dijkstra(graph, source):

Initialize the priority queue

priority_queue = []

# Initialize distances to infinity for all vertices except the source
distances = {vertex: float('infinity') for vertex in graph}
distances[source] = 0

# Push the source node into the priority queue with distance 0
heapq.heappush(priority_queue, (0, source))

while priority_queue:
    # Pop the vertex with the smallest distance
    current_distance, current_vertex = heapq.heappop(priority_queue)

    # If the current distance is greater than the recorded distance, skip it
    if current_distance > distances[current_vertex]:
        continue

    # Check adjacent vertices
    for neighbor, weight in graph[current_vertex].items():
        distance = current_distance + weight

        # Only consider this path if it's better than the known one
        if distance < distances[neighbor]:
            distances[neighbor] = distance
            # Push the updated distance and neighbor into the queue
            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} }

source = 'A' shortest_distances = dijkstra(graph, source) print(shortest_distances) Output: { 'A': 0, 'B': 1, 'C': 3, 'D': 4 } Explanation: Priority Queue (min-heap) is used to efficiently fetch the vertex with the smallest tentative distance. Distances Dictionary is initialized with infinity for all vertices except the source, which starts with a distance of 0. Relaxation Process checks each neighbor of the currently selected vertex, updating distances if a shorter path is found.