# Straightforward Dijkstra in Python

• ``````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:
return

if (cur_row, cur_col) in visited:
continue

# 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
``````

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