我已經實作了 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)
代碼的作用如下：
- 它不是采用第一個最小元素，而是創建所有最小元素的串列。
- 最后它隨機選擇最小的元素之一。
這將既保證 Dijkstra 不變性，又在最便宜的路徑中選擇一條隨機路徑。
uj5u.com熱心網友回復：
可能只是嘗試這樣的事情
random.shuffle(neighbors)
for neighbor in neighbors:
...
它應該隨機訪問鄰居（這假設鄰居是一個串列或元組......如果它首先是一個生成器呼叫串列......
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/390765.html
標籤：Python 蟒蛇-3.x 算法 python-2.7 图形