时间戳

首页 > 解决方案 > 求解 Dijkstra 算法 - 使用两条边传递成本/父母

python - 求解 Dijkstra 算法 - 使用两条边传递成本/父母

问题描述

我有一个这样的图表：

# 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

还有一个父母表：

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可以从多个节点访问的节点？

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

标签： pythonalgorithmgraphdijkstra

解决方案

您不需要使用 more 初始化成本表costs['start'] = 0或使用 more than 初始化父母字典parents = {}。这就是您的算法将为您创建的内容！

您需要进行的唯一其他更改是您的 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)

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

推荐阅读