我已经实作了 Dijkstra 的算法，但我有一个问题。它总是打印相同的最小路径，而可能有其他具有相同权重的路径。

我怎样才能改变我的算法，以便它随机选择具有相同权重的邻居？

我的算法如下：

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

uj5u.com热心网友回复：

        # 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)

代码的作用如下：

1. 它不是采用第一个最小元素，而是创建所有最小元素的串列。
2. 最后它随机选择最小的元素之一。

这将既保证 Dijkstra 不变性，又在最便宜的路径中选择一条随机路径。

uj5u.com热心网友回复：

可能只是尝试这样的事情

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

它应该随机访问邻居（这假设邻居是一个串列或元组......如果它首先是一个生成器呼叫串列......