python - 求解 Dijkstra 算法 - 通过两条边传递成本/双亲

Question

我有一个这样的图表:

# graph table
graph = {}
graph['start'] = {}
graph['start']['a'] = 5
graph['start']['b'] = 2

graph['a'] = {}
graph['a']['c'] = 4
graph['a']['d'] = 2 

graph['b'] = {}
graph['b']['a'] = 8
graph['b']['d'] = 7

graph['c'] = {}
graph['c']['d'] = 6
graph['c']['finish'] = 3

graph['d'] = {}
graph['d']['finish'] = 1
graph['finish'] = {}

我正在尝试找到从 S 到 F 的最快方式。

在本书的第一个示例中，只有一条边连接到一个节点，例如，在此示例中，节点 D 有 3 个权重，并且使用了 cost 表:

costs = {}
infinity = float('inf')
costs['a'] = 5
costs['b'] = 2
costs['c'] = 4 
costs['d'] = # there is 3 costs to node D, which one to select?
costs['finish'] = infinity

还有一个 parent 表:

parents = {}
parents['a'] = 'start' # why not start and b since both `S` and `B` can be `A` nodes parent?
parents['b'] = 'start'
parents['c'] = 'a'
parents['d'] =  # node D can have 3 parents
parents['finish'] = None

但这也有效，我的意思是不会抛出错误，所以我只需要从第一个节点 S 命名父节点？

parents = {}
parents['a'] = 'start' 
parents['b'] = 'start'
parents['finish'] = None

代码:

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float('inf')
    lowest_cost_node = None

    for node in costs:
        cost = costs[node]

        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node



node = find_lowest_cost_node(costs)

while node is not None:
  cost = costs[node]
  neighbors = graph[node]
  for n in neighbors.keys():
      new_cost = cost + neighbors[n]
      if costs[n] > new_cost:
          costs[n] = new_cost
          parents[n] = node
  processed.append(node)
  node = find_lowest_cost_node(costs)


def find_path(parents, finish):
  path = []
  node = finish
  while node:
      path.insert(0, node)
      if parents.__contains__(node):
          node = parents[node]
      else:
          node = None
  return path


path = find_path(parents, 'finish')
distance = costs['finish']

print(f'Path is: {path}')
print(f'Distance from start to finish is: {distance}')

我得到:

Path is: ['finish']
Distance from start to finish is: inf

我的错误在哪里？我应该如何将 cost 和 parent 添加到可以从多个节点访问的节点？

编辑 我确实相信这不是解决这个问题的最佳方法，欢迎提供最佳实践解决方案/建议。

Answer 1

您不需要使用超过 costs['start'] = 0 的成本表或使用超过 parents = {} 的 parent 字典。这就是您的算法将为您创建的内容!

您需要做的唯一其他更改是 while 循环。它只需要检查之前是否已经检测到新节点。如果是，那么我们检查新路径是否更短并根据需要进行更新；如果没有，那么我们建立新路径。

while node is not None:
  cost = costs[node]
  neighbors = graph[node]
  for n in neighbors.keys():
      new_cost = cost + neighbors[n]
      if n in costs:
          if costs[n] > new_cost:
              costs[n] = new_cost
              parents[n] = node
      else:
          costs[n] = new_cost
          parents[n] = node
  processed.append(node)
  node = find_lowest_cost_node(costs)

我认为有很多更简洁的方法来处理图形，但这是使代码按要求工作所需的最小更改。希望对您有帮助!