1. Initialize dist = [inf] * n
  2. Place start in a min heap
  3. For all its neighbors update the dist[v] = dist[u] + d if dist[v] > dist[u] + d and add to min heap
# O(V + E*log(V))
dist = [inf] * (n)
dist[src] = 0
mi_heap = [[0, src]]
visited = set()
while mi_heap:
    dist, u = heappop(mi_heap)
    visited.add(u)
    for v, t in adj[u]:
        if v in visited:
            continue
        if dist[u] + t < dist[v]:
            dist[v] = dist[u] + t
            heappush(mi_heap, [dist[v], v])

Problems

743. Network Delay Time

1631. Path With Minimum Effort

 1dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
 2rows, cols = len(heights), len(heights[0])
 3
 4dp = [[inf for _ in range(cols)] for _ in range(rows)]
 5dp[0][0] = 0
 6mi_heap = [[0, 0, 0]]
 7visited = set()
 8while mi_heap:
 9    d, x, y = heappop(mi_heap)
10
11    visited.add((x, y))
12
13    for d1, d2 in dirs:
14        adj_x = x + d1
15        adj_y = y + d2
16        if 0 <= adj_x < rows and 0 <= adj_y < cols and (adj_x, adj_y) not in visited:
17            mx_diff = max(dp[x][y], abs(heights[adj_x][adj_y] - heights[x][y]))
18            if dp[adj_x][adj_y] > mx_diff:
19                dp[adj_x][adj_y] = mx_diff
20                heappush(mi_heap, [mx_diff, adj_x, adj_y])
21
22return dp[-1][-1]