-
Notifications
You must be signed in to change notification settings - Fork 7
/
dijkstra.py
28 lines (24 loc) · 1.3 KB
/
dijkstra.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def find_shortest_paths(graph, start_point):
visited = [[False for col in row] for row in graph]
distance = [[float('inf') for col in row] for row in graph]
distance[start_point[0]][start_point[1]] = 0
prev_point = [[None for col in row] for row in graph]
n, m = len(graph), len(graph[0])
number_of_points, visited_count = n * m, 0
directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
min_heap = []
heapq.heappush(min_heap, (distance[start_point[0]][start_point[1]], start_point[0], start_point[1]))
while visited_count < number_of_points:
current_point = heapq.heappop(min_heap)
distance_from_start, row, col = current_point
for direction in directions:
new_row, new_col = row + direction[0], col + direction[1]
if -1 < new_row < n and -1 < new_col < m and not visited[new_row][new_col]:
dist_to_new_point = distance_from_start + graph[new_row][new_col]
if dist_to_new_point < distance[new_row][new_col]:
distance[new_row][new_col] = dist_to_new_point
prev_point[new_row][new_col] = (row, col)
heapq.heappush(min_heap, (dist_to_new_point, new_row, new_col))
visited[row][col] = True
visited_count += 1
return distance, prev_point