Dijkstra's Algorithm

Dijkstra's Algorithm computes the shortest path from a starting node to all other nodes in a weighted graph with non-negative edge weights. It is fundamental in computer science and is used in GPS, network routing, and many pathfinding applications.

1. Start with the source node and set its distance to 0. Set all other nodes' distances to infinity.
2. Mark all nodes as unvisited. Set the source as the current node.
3. For the current node, consider all its unvisited neighbors and calculate their tentative distances through the current node.
4. Once all neighbors are considered, mark the current node as visited. A visited node will not be checked again.
5. Select the unvisited node with the smallest tentative distance as the new current node and repeat.
6. Stop when all nodes have been visited or the shortest path to the target node is found.

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [(0, start)]
    while queue:
        curr_dist, curr_node = heapq.heappop(queue)
        if curr_dist > distances[curr_node]:
            continue
        for neighbor, weight in graph[curr_node]:
            distance = curr_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    return distances

# Example usage:
graph = {
    'A': [('B', 2), ('C', 5)],
    'B': [('A', 2), ('C', 1), ('D', 4)],
    'C': [('A', 5), ('B', 1), ('D', 1)],
    'D': [('B', 4), ('C', 1)]
}
print(dijkstra(graph, 'A'))  # {'A': 0, 'B': 2, 'C': 3, 'D': 4}

• Works only with non-negative edge weights.
• Time complexity: O((V + E) log V) with a min-heap (priority queue).
• Used in GPS, network routing, and many pathfinding applications.