Dijkstras算法找不到实际的最短路径

Question

我正在尝试使用三个字典在python中实现dijkstras算法。然而，我并没有从书中得到真正的最短钢琴路径。我的实现不会更新Piano的父级，即使在从节点Drum set到它的路径较短之后也是如此。

这是我的输出：parents-{'Poster': 'Book', 'Rare LP': 'Book', 'Piano': 'Bass guitar', 'Bass guitar': 'Rare LP', 'Drum set': 'Rare LP'} processed-['Poster', 'Rare LP', 'Bass guitar', 'Drum set', 'Piano'] costs-{'Poster': 0, 'Rare LP': 5, 'Bass guitar': 15, 'Drum set': 20, 'Piano': 20}

Desired_result- 父母-{"海报"："书"， "稀有LP"："书"， "钢琴"："架子鼓"， "低音吉他"："稀有LP"， "鼓组"："稀有LP"} 成本-{'海报'： 0， '稀有 LP'： 5， '低音吉他'： 15， '架子鼓'： 20， '钢琴'： 10}

这是我的实现-

import math
# the graph
graph = {'Book':{'Poster':0, 'Rare LP':5}, 'Poster':{'Bass guitar':30, 'Drum set':35},
'Rare LP':{'Bass guitar':15, 'Drum set':20}, 'Bass guitar':{'Piano':20},
'Drum set':{'Piano':10},'Piano':{}}
# the costs table
costs = {'Poster':0, 'Rare LP':5, 'Bass guitar':math.inf, 'Drum set':math.inf, 'Piano':math.inf}
# the parents table
parents = {'Poster':'Book', 'Rare LP':'Book', 'Piano':''}

processed = []
def find_lowest_cost_node(costs):
lowest_cost = math.inf
lowest_cost_node = None
# Go through each node.
for node in costs:
cost = costs[node]
# If it's the lowest cost so far and hasn't been processed yet...
if cost < lowest_cost and node not in processed:
# ... set it as the new lowest-cost node.
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node
# Run till all nodes are processed
while len(processed) < len(graph)-1:
lowest_cost_node = find_lowest_cost_node(costs)
#Loop through neighbours of the current lowest_cost_node
for node in graph[lowest_cost_node].keys():

if costs[node] > costs[lowest_cost_node] + graph[lowest_cost_node][node]:
costs[node] = graph[lowest_cost_node][node]
parents[node] = lowest_cost_node
processed.append(lowest_cost_node)

Answer 1

这部分看起来很可疑：

if costs[node] > costs[lowest_cost_node] + graph[lowest_cost_node][node]:
costs[node] = graph[lowest_cost_node][node]

分配的成本不包括节点的原始成本。

尝试：

if costs[node] > costs[lowest_cost_node] + graph[lowest_cost_node][node]:
costs[node] = costs[lowest_cost_node] + graph[lowest_cost_node][node]