FAQ: Dijkstra's Algorithm: Python - Finishing the Algorithm!

This community-built FAQ covers the “Finishing the Algorithm!” exercise from the lesson “Dijkstra’s Algorithm: Python”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Computer Science

FAQs on the exercise Finishing the Algorithm!

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

Can anyone give some ideas/hints if we want to improve this exercise’s Dijkstra’s algorithm, which kind of data or data structure we should use another than the tuple?

Let’s say, if we change the graph to A -> B = 1, A -> C = 3, B -> C =1. Base on the solution code, each iteration, the vertices_to_explore (as the min heap or next unvisited/updated vertices) becomes:

# 1st iteration: 
[(0, "A")]
# 2nd iteration: 
[(1, "B"), (3, "C")]
# 3rd iteration: 
[(2, "C"), (3, "C"), (3, "D")]
# 4th iteration:
[(3, 'C'), (3, 'D')]
# 5th iteration: 
[(3, 'D')]
# Final iteration:
[(13, 'E')]

I think the “weight” (3) for vertex C coming from A should be replaced or deleted once we find its “weight” (1 + 1 = 2) is actually smaller while coming from B instead. There is no reason that we need to “pop” the “C” twice with two different weights (which means no need to push both into the heap). Same for vertex D, one is from vertex B, another one is from vertex C, even though they have the same weight.

Tried to improve it but realized that the tuple is immutable, and the dictionary is unordered which is harder to use it into the heap. I’d appreciate if anyone can give some thoughts. :grinning:

1 Like

Can anyone assist with this, I’m having a bit of trouble understanding the “verticies_to_explore” aspect,

for neighbor, edge_weight in graph[current_vertex]

should be referring to the neighbors for “A” which should only, B & C,
I’m a bit unsure how it goes where in the code it gets us to nodes D & E

Full cod eto the solution below:

raph = {
        'A': [('B', 10), ('C', 3)],
        'C': [('D', 2)],
        'D': [('E', 10)],
        'E': [('A', 7)],
        'B': [('C', 3), ('D', 2)]

def dijkstras(graph, start):
  distances = {}
  for vertex in graph:
    distances[vertex] = inf
  distances[start] = 0
  vertices_to_explore = [(0, start)]
  while vertices_to_explore:
    current_distance, current_vertex = heappop(vertices_to_explore)
    for neighbor, edge_weight in graph[current_vertex]:
      new_distance = current_distance + edge_weight
      if new_distance < distances[neighbor]:
        distances[neighbor] = new_distance
        heappush(vertices_to_explore, (new_distance, neighbor))
  return distances
distances_from_d = dijkstras(graph, 'D')
print("\n\nShortest Distances: {0}".format(distances_from_d))


for neighbor, edge_weight in graph[current_vertex]

let’s assume current_ vertex is “A”.
when we look at the graph dictionary we can see the connections: ‘A’: [(‘B’, 10), (‘C’, 3)],

therefor you can also read it like:

for neighbor, edge_weight in graph[current_vertex]

for “B” , 10 in graph ‘A’: [(‘B’, 10), (‘C’, 3)]
new_distance = 0 + 10

Personal I like to comment and print out a lot, to make sure I understand it correctly.
Here is my code with comments, maybe that’s also helpful.

#___________________Dijkstra Algorithm_______________________________________

def dijkstras(graph,start_vertex):
	#__Instantiating a distance dictionary that will eventually map vertecies
	# to their distanc from the start vertex
	distances = {}

	#__Loop through each vertex in graph and set its corresponding value within distances equal to inf
	for vertex in graph:
		distances[vertex] = inf

	#__settingt the start vertex to 0
	distances[start_vertex] = 0

	#__this tulpe represents the start vertex within the min - heap-list
	#______ HEAP LIST
	vertices_to_explore = [(0,start_vertex)]

	First, we’ll traverse the vertices_to_explore heap until it is empty, 
	popping off the vertex with the minimum distance from start. 
	Inside our while loop, we’ll iterate over the neighboring vertices of 
	current_vertex and add each neighbor (and its distance from start) 
	to the vertices_to_explore min-heap.


	#__as long theire is content in verticies to explore
	while vertices_to_explore:
		#__this will always be the vertex with the minimum distance from start
		current_distance,current_vertex = heappop(vertices_to_explore)
		print("\nThis is the current vertex: {0} with the distance: {1}".format(current_vertex,current_distance))
		#__Identify neighbor‘s distance from start
		for neighbor,edge_weight in graph[current_vertex]:
			new_distance = current_distance + edge_weight
			print("\nThis is the neighbor: {0} with the distance: {1}".format(neighbor,edge_weight))
			print("The distance from the start vertex \"{0}\" to its neighbor \"{1}\" is: {2}".format(start_vertex,neighbor,new_distance))
			#_____comparing the distances and replacing them in heap list
			if new_distance < distances[neighbor]:
				distances[neighbor] = new_distance
				heappush(vertices_to_explore, (new_distance, neighbor))
				print("Pushing the neigbor into the Heap List.....")

	# getting the minimum distance
	del distances[start_vertex]
	minimum_distance = min(distances.values())
	minimum_vertex = (list(distances.keys())[list(distances.values()).index(minimum_distance)])

	print("\nThe shortest distance is from \"{0}\" to \"{1}\". Weight: {2}".format(start_vertex,minimum_vertex,minimum_distance))
	#return distances



1 Like

How can heappop be directly called on vertices_to_explore. Isn’t is supposed to he called only on heapq data type?

This implementation does not use a list to keep track of which vertices have been visited. Why is it that checking to see if the new distance is less than the distance in the dictionary is enough to prevent you from revisiting nodes?

1 Like

heapq is a library of functions that work on heaps, which are usually stored as lists. So you can take any old ordinary list and apply the heapq functions and they will not throw any errors. However, the functions may not work if the list is already a non-heapy list. For example, if you have a random list of numbers and then call heappush, its not going to come out as a heap.

from heapq import heappush import random random.seed() nonheap = [random.randint(1,10) for blah in range(10)] print("Not a heap: ") print(nonheap) heappush(nonheap, 2.5) print("Still not a heap: ") print(nonheap)

You have to start with something that is already a heap (which might be an empty list) in order to use heapq methods rightly.

from heapq import heappush import random random.seed() #empty list heap = [] #add random numbers using heappush for count in range(10): heappush(heap, random.randint(1,10)) print(heap) print("Now it will work:") heappush(heap, 2.5) print(heap)