Straightforward Dijkstra in Python

  • 0
    from heapq import heappush, heappop
    class Solution(object):
        def shortestDistance(self, maze, start, destination):
            # Once a 'node' updates its neighbors' distances through it, it is marked visited.
            visited = set()
            best_dist = {} # Not in here means infinity.
            best_dist[tuple(start)] = 0
            fringe = []
            heappush(fringe, (0, tuple(start)[0], tuple(start)[1]))
            self.dijkstra_explore(maze, destination, visited, best_dist, fringe)
            if tuple(destination) not in best_dist:
                return -1
            return best_dist[tuple(destination)]
        def dijkstra_explore(self, maze, destination, visited, best_dist, fringe):
            while fringe:
                visit = heappop(fringe)
                cur_dist, cur_row, cur_col = visit
                if (cur_row, cur_col) == destination:
                if (cur_row, cur_col) in visited:
                visited.add((cur_row, cur_col))
                # Get unvisited neighbors, update neighbors' best dist.
                neighbors = self.get_neighbors(maze, cur_row, cur_col, visited)
                for new_row, new_col, dist_to_neighbor in neighbors:
                    prev_neighbor_dist = best_dist.get((new_row, new_col), float('inf'))
                    best_dist_to_neighbor = min(prev_neighbor_dist, dist_to_neighbor + cur_dist)
                    if best_dist_to_neighbor != prev_neighbor_dist:
                        heappush(fringe, (best_dist_to_neighbor, new_row, new_col))
                        # No need to remove the previous entry in fringe for (new_row, new_col), if exists, becuase --
                        # This newly pushed entry has a dist less than the exsiting one, so will be visited first.
                        # When that previous entry is visited, it will be ignored per the 'if in visited: continue' check.
                        best_dist[(new_row, new_col)] = best_dist_to_neighbor
        def get_neighbors(self, maze, row, col, visited):
            # (row, col) is a 0 position. returns all possible neighbors.
            offsets = [[0, 1], [0, -1], [1, 0], [-1, 0]]
            neighbors = []
            for offset in offsets:
                cur_row, cur_col = row, col
                while 0 <= cur_row < len(maze) and \
                      0 <= cur_col < len(maze[0]) and \
                      maze[cur_row][cur_col] == 0:
                    cur_row += offset[0]; cur_col += offset[1]
                new_row, new_col = cur_row - offset[0], cur_col - offset[1]
                dist_to_neighbor = abs(-row -col + new_row + new_col) 
                if dist_to_neighbor != 0 and (new_row, new_col) not in visited:
                    neighbors.append((new_row, new_col, dist_to_neighbor))
            return neighbors

Log in to reply

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