Question: Dijkstra's Algorithm to compute shortest path-- I can't figure out why my code doesn't work. Please help! This is my last assignment for this course.

Dijkstra's Algorithm to compute shortest path-- I can't figure out why my code doesn't work. Please help! This is my last assignment for this course. Please and Thank you!

Dijkstra's Algorithm to compute shortest path-- I can't figure out why mycode doesn't work. Please help! This is my last assignment for thiscourse. Please and Thank you!# your code here***q = PriorityQueue()source = graph.get_vertex_from_coords(source_coordinates[0],source_coordinates[1])d = graph.get_vertex_from_coords(dest_coordinates[0], dest_coordinates[1])source.d = 0q.insert(source)while not q.is_empty():u = q.get_and_delete_min()u.processed = Trueifu.x == d.x and u.y == d.y:shortest_path_distance = u.dbreakfor k in range(len(graph.get_list_of_neighbors(u))):v= graph.get_list_of_neighbors(u)[k][0]w = graph.get_list_of_neighbors(u)[k][1]if v.processed == False and v.d > (u.d +w):v.d = u.d + wv.pi = uif v.idx_in_priority_queue == -1:q.insert(v)else:q.update_vertex_weight(v)path = [(d.x,d.y)]nextnode = dwhile nextnode != source:path.insert(0,(nextnode.pi.x, nextnode.pi.y))nextnode = nextnode.pireturn path, shortest_path_distance          student submitted image, transcription available belowstudent submitted image, transcription available belowstudent submitted image, transcription available below


# your code here***

q = PriorityQueue()

source = graph.get_vertex_from_coords(source_coordinates[0], source_coordinates[1])
d = graph.get_vertex_from_coords(dest_coordinates[0], dest_coordinates[1])

source.d = 0
q.insert(source)


while not q.is_empty():
u = q.get_and_delete_min()
u.processed = True


if u.x == d.x and u.y == d.y:
shortest_path_distance = u.d
break

for k in range(len(graph.get_list_of_neighbors(u))):
v = graph.get_list_of_neighbors(u)[k][0]
w = graph.get_list_of_neighbors(u)[k][1]

if v.processed == False and v.d > (u.d + w):

v.d = u.d + w
v.pi = u

if v.idx_in_priority_queue == -1:
q.insert(v)

else:
q.update_vertex_weight(v)


path = [(d.x, d.y)]
nextnode = d
while nextnode != source:
path.insert(0,(nextnode.pi.x, nextnode.pi.y))
nextnode = nextnode.pi

return path, shortest_path_distance
 
 
 
 
 
 
 
 
 
 

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!