Use a min-heap ordered by distance:
function dijkstra(n, adj, start):
dist = array of size n + 1, all infinity
dist[start] = 0
pq = min-heap with (0, start)
while pq is not empty:
(d, u) = pq.pop()
if d > dist[u]:
continue
for (v, w) in adj[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
pq.push((dist[v], v))
return dist
Time: . Space: .