# python dijkstra's algorithm AC with heapq, just for fun : )

• There are already great DP solutions in O(mn), but it seems there is not yet an accepted solution using dijkstra's algorithm. The time complexity is O(mn * log(mn)) by using a heapq.

``````import heapq

class Solution(object):
def minPathSum(self, grid):
m = len(grid)
if m == 0:
return 0

n = len(grid[0])
if n == 0:
return 0

distTo = [ [float('inf') for j in range(n)] for i in range(m)]
distTo[0][0] = grid[0][0]

visited = [ [False for j in range(n)] for i in range(m)]

# note: we do not need to change in heapq,
# we can just keep pushing and the smallest will win
# (distance, (i, j))
pq = [(grid[0][0], (0, 0))]

while True:
if not pq:
return distTo[m-1][n-1]

i, j = heapq.heappop(pq)[1]
if visited[i][j]:
continue

visited[i][j] = True

if (i, j) == (m - 1, n - 1):
return distTo[m-1][n-1]

if i < m - 1:
down = distTo[i][j] + grid[i + 1][j]
if down < distTo[i + 1][j]:
distTo[i + 1][j] = down
heapq.heappush(pq, (down, (i + 1, j)))

if j < n - 1:
right = distTo[i][j] + grid[i][j + 1]
if right < distTo[i][j + 1]:
distTo[i][j + 1] = right
heapq.heappush(pq, (right, (i, j + 1)))

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.