1import heapq
2
3def dijkstra(graph, start):
4 pq = [(0, start)]
5 dist = {node: float('inf') for node in graph}
6 dist[start] = 0
7 visited = set()
8 while pq:
9 d, u = heapq.heappop(pq)
10 if u in visited:
11 continue
12 visited.add(u)
13 for v, weight in graph[u]:
14 if v not in visited:
15 new_dist = dist[u] + weight
16 if new_dist < dist[v]:
17 dist[v] = new_dist
18 heapq.heappush(pq, (new_dist, v))
19 return dist