class PriorityQueue: def __init__(self): self.heap = [] def get_parent(self, node_idx): return (node_idx-1) // 2 def get_left_child(self, node_idx): return node_idx * 2 + 1 def get_right_child(self, node_idx): return node_idx * 2 + 2

def sift_down(self, node_idx): left_idx = self.get_left_child(node_idx) right_idx = self.get_right_child(node_idx) smallest_idx = node_idx if left_idx < len(self.heap) and self.heap[left_idx] < self.heap[smallest_idx]: smallest_idx = left_idx if right_idx < len(self.heap) and self.heap[right_idx] < self.heap[smallest_idx]: smallest_idx = right_idx if smallest_idx != node_idx: self.heap[node_idx], self.heap[smallest_idx] = self.heap[smallest_idx], self.heap[node_idx] return self.sift_down(smallest_idx) def sift_up(self, node_idx): if node_idx == 0: return root_idx = self.get_parent(node_idx) if self.heap[node_idx] < self.heap[root_idx]: self.heap[node_idx], self.heap[root_idx] = self.heap[root_idx], self.heap[node_idx] return self.sift_up(root_idx) """ Extracts the minimum value from the priority queue """ def extract_min(self): last = len(self.heap)-1 self.heap[0], self.heap[last] = self.heap[last], self.heap[0] extract = self.heap.pop() self.sift_down(0) return extract """ Adds a new value to the priority queue """ def append(self, value): self.heap.append(value) self.sift_up(len(self.heap) - 1) def is_empty(self): return len(self.heap) == 0

""" This function returns a tuple of (neighbor_cost, neighbor_cell) """ def get_neighbors(graph, node): def is_valid(node): return ( node[0] >= 0 and node[1] >= 0 and \ node[1] < len(graph) and node[0] < len(graph[0]) and \ graph[node[1]][node[0]] != -1 ) neighbors = [] for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]: neighbor_x, neighbor_y = [node[i] + direction[i] for i in range(2)] potential_neighbor = (neighbor_x, neighbor_y) if is_valid(potential_neighbor): neighbors.append((graph[neighbor_y][neighbor_x], potential_neighbor)) return neighbors

def dijkstra(graph, start, goal): # initialize variables parent = {} # holds mapping between every node and it's parent in the path current_node = start closed_set = set() cost_dict = {} # initialize open queue open_queue = PriorityQueue() open_queue.append((0, start)) # while loop setting current node while not open_queue.is_empty(): current_node_cost, current_node = open_queue.extract_min() """ Check if the node is on the closed set, if it's then do nothing """ if current_node in closed_set: continue

if current_node == goal: """ Return the cost """ path = [goal] node = goal while node != start: node = parent[node] path.append(node) path.reverse() return (cost_dict[goal], path) # iterate over neighbors of current node # and add to open queue if not already there or in closed for neighbor in get_neighbors(graph, current_node): neighbor_cost, neighbor_node = neighbor """ Now we need to calculate the cost to reach this neighbor via current_node remember, the cost is the cost to the current_node + the cost of the edge (neighbor cost) """ # fill the following line new_cost = # your code here if neighbor_node in closed_set: continue if neighbor_node in cost_dict and cost_dict[neighbor_node] <= new_cost: continue cost_dict[neighbor_node] = new_cost """ Store parent info """ # fill this line """ Now we need to add the new cost and the neighbor node to the queue, make a tuple of the new cost and the neighbor node """ # Fill the following line open_queue.append(()) closed_set.add(current_node) return None

Instruction:

Dijkstra's Algorithm

In this exercise, we will implement Dijkstra's for a maze with walls. The function, dijkstra(), takes three arguments: the graph to traverse, the start node, and the end node. The start and end nodes will be given as tuples (e.g. (0,0) or (9,2)). The graph will be supplied as a matrix. The value in a cell is the cost to enter that cell. Walls are marked with -1. The start and end nodes are guaranteed to be valid positions in the matrix.

It should return a path from start to node, inclusive, as a list, as well at the total cost of the path. The cost should come first in the return tuple.

1. Create an empty set of closed nodes and an empty dictionary to store each node's parent and the cost to get to it

2. Initialize a priority queue for the open nodes containing the start node.

3. While the open queue is not empty, dequeue the next node from the open queue and set it to the current node

1. If the node is in the closed set, continue to the next node

2. If it is the goal node, reconstruct the path back to the start using the parent mapping

3. Otherwise, for each of its neighbors,

1. If the node is in the closed set, continue to the next node

2. Calculate the cost to get to this node

3. If the node has no entry in the cost dict or the current cost is less than the one stored, add it to the priority queue with the current cost and set its parent to the current node

Add the current node to the closed set

4. If you empty the open queue without reaching the goal node, there is no path

The algorithm is mostly implemented for you with only few lines for you to fill, I have provided comments above the lines.

You need to fill the following three lines

Lines 128, 139, 146

graph1 = [

[ 1, 1, -1, 1, 1],

[ 1, 1, -1, 1, 1],

[ 1, 1, 25, 9, 1],

[ 1, -1, -1, 1, 1],

[ 1, 1, -1, 1, 7],

[12, 1, 50, 1, 1],

[ 1, 1, 39, 1, 1],

]

start = (0, 0)

goal = (4, 0)

dijkstra(graph1, start, goal)

=> (40, [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (3, 2),

(3, 1), (3, 0), (4, 0)])

graph2 = [

[ 1, 1, -1, 1, 1],

[ 1, 1, -1, 1, 1],

[ 1, 1, 1, 9, 1],

[ 1, -1, -1, 1, 1],

[ 1, 1, -1, 1, 7],

[12, 1, 50, 1, 1],

[ 1, 1, 39, 1, 1],

]

dijkstra(graph2, start, goal)

=> (16, [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (3, 2),

(3, 1), (3, 0), (4, 0)])

graph3 = [

[ 1, 1, -1, 1, 1],

[ 1, 1, -1, 1, 1],

[ 1, 1, 25, 9, 1],

[ 1, -1, -1, 1, 1],

[ 1, 1, -1, 1, 7],

[12, 1, 1, 1, 1],

[ 1, 1, 1, 1, 1],

]

dijkstra(graph3, start, goal)

=> (14, [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 4),

(1, 5), (2, 5), (3, 5), (3, 4), (3, 3), (4, 3), (4, 2),

(4, 1), (4, 0)])