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 () 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 () below!
Agree with a comment or answer? Like () to up-vote the contribution!
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:
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.
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
dijkstras(graph,"A")
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?
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)
) below.
) to up-vote the contribution!
