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


  • 0
    1

    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
    

Log in to reply
 

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