I have implemented Dijkstra's algorithm but I have a problem. It always prints the same minimum path while there may be other paths with the same weight.

How could I change my algorithm so that it randomly selects the neighbors with the same weight?

My algorithm is below:

def dijkstra_algorithm(graph, start_node):
    unvisited_nodes = list(graph.get_nodes())
 
    # We'll use this dict to save the cost of visiting each node and update it as we move along the graph   
    shortest_path = {}
 
    # We'll use this dict to save the shortest known path to a node found so far
    previous_nodes = {}
 
    # We'll use max_value to initialize the "infinity" value of the unvisited nodes   
    max_value = sys.maxsize
    for node in unvisited_nodes:
        shortest_path[node] = max_value
    # However, we initialize the starting node's value with 0   
    shortest_path[start_node] = 0
    
    # The algorithm executes until we visit all nodes
    while unvisited_nodes:
        # The code block below finds the node with the lowest score
        current_min_node = None
        for node in unvisited_nodes: # Iterate over the nodes
            if current_min_node == None:
                current_min_node = node
            elif shortest_path[node] < shortest_path[current_min_node]:
                current_min_node = node
                
        # The code block below retrieves the current node's neighbors and updates their distances
        neighbors = graph.get_outgoing_edges(current_min_node)
        for neighbor in neighbors:
            tentative_value = shortest_path[current_min_node]   graph.value(current_min_node, neighbor)
            if tentative_value < shortest_path[neighbor]:
                shortest_path[neighbor] = tentative_value
                # We also update the best path to the current node
                previous_nodes[neighbor] = current_min_node
 
        # After visiting its neighbors, we mark the node as "visited"
        unvisited_nodes.remove(current_min_node)
    
    return previous_nodes, shortest_path

CodePudding user response：

        # The code block below finds all the min nodes
        # and randomly chooses one for traversal
        min_nodes = []
        for node in unvisited_nodes: # Iterate over the nodes
            if len(min_nodes) == 0:
                min_nodes.append(node)
            elif shortest_path[node] < shortest_path[min_nodes[0]]:
                min_nodes = [node]
            else:
            # this is the case where 2 nodes have the same cost
            # we are going to take all of them
            # and at the end choose one randomly
                min_nodes.append(node)
        current_min_node = random.choice(min_nodes)

What the code does is as follows:

1. Instead of taking the first smallest element, it creates a list of all the smallest elements.
2. At the end it choose one of the smallest elements randomly.

This will both guarantee the Dijkstra invariant and choose a random path among the cheapest.

CodePudding user response：

probably just try something like this

random.shuffle(neighbors)
for neighbor in neighbors:
    ...

which should visit the neighbors randomly (this assumes neighbors is a list or tuple... if its a generator call list on it first...