Dijkstra's Algorithm

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source to all other nodes in a graph with non-negative weights. It uses a min-heap (priority queue) for efficiency.

      4
  0 ——— 1
  |     |
1 |     | 1
  |     |
  2 ——— 3
      2

dijkstra(graph, 0):
  dist[0] = 0
  dist[1] = 3   (0→2→1, cost 1+2=3, faster than direct edge 4)
  dist[2] = 1
  dist[3] = 3   (0→2→3, cost 1+2)

Algorithm

import heapq

def dijkstra(graph, start):
    # graph = {node: [(neighbor, weight), ...]}
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]    # (distance, node)

    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue        # outdated entry
        for nb, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[nb]:
                dist[nb] = new_dist
                heapq.heappush(heap, (new_dist, nb))

    return dist

Complexity

• Time: O((V + E) log V) with a binary heap
• Space: O(V)
• Limitation: Doesn't work with negative edge weights (use Bellman-Ford instead)

Your Task

Implement dijkstra(graph, start) that returns a dictionary of shortest distances from start to every other node. The graph is a dict {node: [(neighbor, weight), ...]}.