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


  • 0

    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)))
    
    

Log in to reply
 

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