# Python implementation of Dijkstra Algorithm with detailed comments(beating 99%)

• This is a typical problem where we can use uniform-cost search algorithm(Dijkstra's algorithm). We should note that whenever we update the distance of a node that is already in the max-heap, we need to re-heapify the max-heap to retain the heap invariance.

``````from heapq import *
class Solution(object):
def shortestDistance(self, maze, start, destination):
"""
:type maze: List[List[int]]
:type start: List[int]
:type destination: List[int]
:rtype: int
"""
root = [0, tuple(start)]
queue = [root]
# save the reference of the corresponding node of a state, for fast look-up
node_ref = {tuple(start): root}
# save the shortest distance from start to every other state, you can also regard it as a visited set
min_dist = {tuple(start):0}
while len(queue):
# when a node is popped out, the shortest distance from start to this node is found
d, state = heappop(queue)
# add it to min_dist
min_dist[state] = d
i, j = state
# remove it from node_ref
node_ref.pop(state)
if list(state) == destination:
return d
modified = False
t_j = j
dist = 0
while t_j > 0 and maze[i][t_j - 1] != 1:# roll left
dist += 1
t_j -= 1
# if shortest distance to (i, t_j) is not found((i, t_j) is not visited), update the distance
if (i, t_j) not in min_dist:
# if state is not in max-heap, then create a node to represent it and push it into max-heap, and save the node's reference in node_ref
if (i, t_j) not in node_ref:
node = [d + dist, (i, t_j)]
node_ref[(i, t_j)] = node
heappush(queue, node)
# if state is in max-heap, update it distance
else:
# we modify the corresponding node in the max-heap
modified = True
node = node_ref[(i, t_j)]
node[0] = min(node[0], d + dist)
t_i = i
dist = 0
while t_i > 0 and maze[t_i - 1][j] != 1:# roll up
dist += 1
t_i -= 1
if (t_i, j) not in min_dist:
if (t_i, j) not in node_ref:
node = [d + dist, (t_i, j)]
node_ref[(t_i, j)] = node
heappush(queue, node)
else:
modified = True
node = node_ref[(t_i, j)]
node[0] = min(node[0], d + dist)
t_j = j
dist = 0
while t_j < len(maze[0]) - 1 and maze[i][t_j + 1] != 1:# roll right
dist += 1
t_j += 1
if (i, t_j) not in min_dist:
if (i, t_j) not in node_ref:
node = [d + dist, (i, t_j)]
node_ref[(i, t_j)] = node
heappush(queue, node)
else:
modified = True
node = node_ref[(i, t_j)]
node[0] = min(node[0], d + dist)
t_i = i
dist = 0
while t_i < len(maze) - 1 and maze[t_i + 1][j] != 1:# roll down
dist += 1
t_i += 1
if (t_i, j) not in min_dist:
if (t_i, j) not in node_ref:
node = [d + dist, (t_i, j)]
node_ref[(t_i, j)] = node
heappush(queue, node)
else:
modified = True
node = node_ref[(t_i, j)]
node[0] = min(node[0], d + dist)
#if some nodes in the max-heap are modified, then heapify the max-heap to retain the heap invariance
if modified:
heapify(queue)
return -1
``````

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