I have implemented a dijkstra algorithm that calculates the shortest distance for every node from the start node, but I am not able to retrieve the shortest path for these nodes. I watched a youtube video, and then tried to implement the steps that he did in python. I did not follow a specific psuedocode. Also, if anybody could please tell me if there is anything wrong with my code.
def dijkstra(start_id: int,end_id:int,graph:Dict):
'''
TODO: Implement dijkstra, change the parameters if you wish so.
'''
#make a list for all of the paths
paths = []
# Is a list for all of the visited nodes
visited_nodes = []
# make a table that stores all of the values of the nodes
table = {v:float("inf") for v in graph}
# Set the start id value in the table to 0
table[start_id] = 0
# Make the minimum that is going to be compared with equal to inifinity in the start
minimum = float("inf")
# The path should contain the start id at the start
path = [start_id]
# Make a while statement that the operation keeps going until every node is visited
while end_id not in visited_nodes:
# Explore the edges of the node
for edge in graph.get(path[-1]):
#if edge == end_id:
# If there is only one element in the path
if len(path) <= 1:
# We are going to compare it directly with itself not any before nodes
if graph[path[-1]][edge] < table[edge]:
table[edge] = graph[path[-1]][edge]
# This is the normal conditions
if len(path)> 1:
# Compare the weight of this edge + the weigh of the previous edge
if graph[path[-1]][edge] + table[path[-2]] < table[edge]:
table[edge] = graph[path[-1]][edge] + table[path[-2]]
# We then add the node to its edges were explored to the visited list
visited_nodes.append(path[-1])
# This is just added to be able to add the last node that was not explored
if len(visited_nodes) < len(graph)-1:
# Now we choose the next node to be explored, by looping through all the nodes in the set
for node in table:
# Only if the node is not in the visited list it will be explored
if node not in visited_nodes:
if table[node] < minimum:
minimum = table[node]
minimum_node = node
path.append(minimum_node)
else:
# Will add the last node that was not added
for node in table:
if node not in visited_nodes:
path.append(node)
# print(minimum_node)
paths.append(path)
return table
I have tried to implement the dijkstra algorithm in my own way, but the task that I am solving requires me to return the shortest path between two nodes
