求解 Dijkstra 算法 - 通过成本 / parents 有两条边

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 table :

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 table:

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 = {}
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添加到可以从1个以上节点访问的节点？[=25=]

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

Answer 1

您不需要初始化成本 table 超过 costs['start'] = 0 或 parents 字典超过 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)

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

求解 Dijkstra 算法 - 通过成本 / parents 有两条边

Solving Dijkstra's algorithm - passing costs / parents with two edges

python

algorithm

graph

dijkstra