Skip to content

Instantly share code, notes, and snippets.

@VXU1230
Last active August 13, 2021 02:28
Show Gist options
  • Save VXU1230/7b82105d00f2573c2e9615c493616f54 to your computer and use it in GitHub Desktop.
Save VXU1230/7b82105d00f2573c2e9615c493616f54 to your computer and use it in GitHub Desktop.
def dijkstra(grid):
if grid[0][0] == 1 or grid[-1][-1] == 1:
return -1
n = len(grid)
heap = []
seen = set()
heapq.heappush(heap, (1, 1, 0, 0))
cache = {(0, 0): 1}
while heap:
(cost, dist, x, y) = heapq.heappop(heap)
print("({},{})".format(x, y), end=" ")
if x == n - 1 and y == n - 1:
return dist
if (x,y) not in seen:
seen.add((x, y))
for (nei_x, nei_y) in get_nei(x, y):
if 0 <= nei_x < n and 0 <= nei_y < n and grid[nei_x][nei_y] == 0:
new_dist = dist + 1
if new_dist < cache.get((nei_x, nei_y), float('inf')):
cache[(nei_x, nei_y)] = new_dist
heapq.heappush(heap, (new_dist, new_dist, nei_x, nei_y))
return -1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment