0

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

2
  • "implement the dijkstra algorithm in my own way": where is the priority queue? Commented Oct 5, 2023 at 7:20
  • Do I always have to use the priority queue method for the dijkstra algorithm? Commented Oct 6, 2023 at 16:31

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.