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

Question

我正在尝试使用三个词典在 python 中实现 dijkstras 算法。但是，我没有从 Book 获得通往钢琴的真正最短路径。即使在从节点 Drum set.

到它的更短路径之后，我的实现也不会更新 Piano 的 parent

这是我的输出： 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- parents-{'Poster': 'Book', 'Rare LP': 'Book', 'Piano': 'Drum set', 'Bass guitar': 'Rare LP', 'Drum set': 'Rare LP'} 成本-{'Poster': 0, 'Rare LP': 5, 'Bass guitar': 15, 'Drum set': 20, 'Piano': 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]

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

dijkstras algorithm doesn't find the actual shortest path

python

algorithm

dijkstra