What is Dijkstra's algorithm?

Dijkstra's algorithm finds the shortest paths from a single starting vertex to all other vertices in a weighted directed or undirected graph with non-negative edge weights.

Working principle:

1. Initialization: Assign a distance of 0 to the starting vertex and infinity to all others. All vertices except the starting one are marked as unvisited.
2. Iteration: While there are unvisited vertices:
   • Select the unvisited vertex with the smallest current distance.
   • Mark it as visited.
   • For all its neighbors, if the path through the current vertex is shorter than the current shortest path to the neighbor, update the distance to the neighbor.

Data structures:

• Often a priority queue (e.g., based on a heap) is used for efficient selection of the vertex with the minimum distance.
• An array or dictionary is used to store the current shortest distances.

Constraints:

• Works only with non-negative edge weights.

# Example implementation in Python using heapq for the priority queue
import heapq

def dijkstra(graph, start_node):
    distances = {node: float('inf') for node in graph} # Initialization of distances
    distances[start_node] = 0 # Distance to the starting vertex is 0
    priority_queue = [(0, start_node)] # Priority queue: (distance, vertex)

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

        if current_distance > distances[current_node]: # If a shorter path has already been found, skip
            continue

        for neighbor, weight in graph[current_node].items(): # Check neighbors
            distance = current_distance + weight # Calculate new distance

            if distance < distances[neighbor]: # If the new path is shorter
                distances[neighbor] = distance # Update the distance
                heapq.heappush(priority_queue, (distance, neighbor)) # Add neighbor to the queue

    return distances

# Example graph represented as an adjacency dictionary: {node: {neighbor: weight}}
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) # {'A': 0, 'B': 1, 'C': 3, 'D': 4}