为什么这个最短寻路算法不起作用？

Question

尝试通过动态规划方法找到最短路径 但下面的算法代码和图形类似乎不起作用。

我厌倦了通过备忘录技术存储路径以及成本，因此不会发生冗余计算，但它仍然给了我最大的递归深度并且找不到最短路径。

class Graph:
  def __init__(self):
      self.nodes = dict()

  def add_edge(self, p, c, weight):
    if self.nodes.get(p, -1) == -1 or self.nodes.get(c, -1) == -1:
      return

    self.nodes[p].append((c, weight))
    self.nodes[c].append((p, weight))

  def add_node(self, n):
    if self.nodes.get(n, -1) != -1:
      return 

    self.nodes[n] = []

  def is_adjacent(self, a, b):
     for i in self.nodes[a]:
      if i[0] == b:
        return True

     return False



def weight(graph, a, b):
  if graph.is_adjacent(a, b) == False:
    return "Not adjacent"

  for i in graph.nodes[a]:
    if i[0] == b:
      return i[1]


def path_length(graph, path):
  sum = 0
  for i in  range(0, len(path) - 1):
    
    if weight(graph, path[i] , path[i + 1]) == "Not adjacent":
      return "Invalid path"

    sum = sum + weight(graph, path[i], path[i + 1])

  return sum


memo = dict()
costs = dict()

def shortest_path(graph, root, target):
    if memo.get(root + ' , ' + target, -1) != -1:
      return memo[root + ' , ' + target]

    if root == target:
      memo[root + ' , ' + target] = [root]
      costs[ [root] ] = 0
      return memo[root + ' , ' + target]

    if graph.nodes[root] == []:            #childless node
      memo[root + ' , ' + target] = []
      return memo[root + ' , ' + target]

    spaths = []  # spaths is a list for shortest paths from adjacent nodes
    for i in graph.nodes[root]:
      adjacent_node = i[0]
      spaths.append( shortest_path(graph , adjacent_node, target) )

    shortestPath = []
    minimum_cost = 1000000000

    for i in spaths:
      if i[-1] != target or i == []:
        continue

      if costs.get(i, -1) == - 1:
        if  minimum_cost > path_length(graph, i) + weight(graph, root, i[0]):
            minimum_cost = path_length(graph, i) + weight(graph ,root, i[0])

            costs[i] = path_length(graph, i)
        
            shortestPath = []
            shortestPath.append(root)
            for j in i:
              shortestPath.append(j)

      if costs[i] + weight(graph, root, i[0]) > minimum_cost:
        minimum_cost = costs[i] + weight(graph, root, i[0])

        shortestPath = []
        shortestPath.append(root)
        for j in i:
              shortestPath.append(j)

    memo[root + ' , ' + target] = shortestPath

    return memo[root + ' , ' + target]

nodes_ =  {
    'A' : [ ('B', 4) , ('H', 8) ],
    'B' : [ ('A', 4) ,  ('C', 8) , ('H', 11)],
    'C'  :[ ('B', 8), ('D', 7), ('F', 4), ('I', 2)],
    'D' : [ ('C', 7), ('E', 9), ('F', 14)],
    'E' : [('D', 9), ('F', 10)],
    'F' : [('C', 4), ('D', 14), ('E', 10), ('G', 2)],
    'G' : [('F', 2), ('H', 1), ('I', 6)],
    'H' : [('A', 8), ('B', 11) ,('G', 1), ('I', 7)],
    'I' : [('C', 2), ('G', 6), ('H', 7)]
}

g = Graph()
g.nodes = nodes_

shortest_path(g, 'A', 'I')

当我尝试代码时，它给了我最大的递归深度

Answer 1

无限递归的原因在这里：

    for i in graph.nodes[root]:
      adjacent_node = i[0]
      spaths.append( shortest_path(graph , adjacent_node, target) )

由于您的图是无向的，如果节点 𝑎 将 𝑏 作为邻居，那么 𝑏 将 𝑎 作为邻居。如果他们是彼此的first邻居，那么你就会陷入递归循环。

您的示例图就是这种情况：节点“A”的第一个邻居是节点“B”，反之亦然。

root

首先等于“A”，

i[0]

将等于“B”。然后进行递归调用，使

root

等于“B”。现在发生了相反的情况：

i[0]

现在是“A”，并且进行了递归调用，这并不会让我们更接近解决方案，而只是重复相同的循环。

另一个问题是您的代码会尝试使用列表作为字典中的键

c

，但这是不可能的。您不能使用列表作为字典键。

没问题，但你似乎经常使用这种模式：

if self.nodes.get(n, -1) != -1:

您可以简单地使用

in

运算符来完成此操作：

if n in self.nodes:

Dijkstra 算法

在处理最短路径问题时，它是本网站上提到最多的算法之一。您可以在 Stack Overflow 上找到数百种实现。我将在这里展示一个使用您的

Graph

数据结构和

heapq

的优先级队列，这是 Dijkstra 算法的典型特征：

from heapq import heappush, heappop

def shortest_path(graph, root, target):
    heap = [(0, root, None)]  # weight, node, previousnode
    camefrom = {}
    
    while heap:
        cost, node, previousnode = heappop(heap)
        if node == target:
            # bingo! unwind path
            path = [target]
            while previousnode:
                path.append(previousnode)
                previousnode = camefrom[previousnode]
            return path[::-1]
        if node not in camefrom:
            camefrom[node] = previousnode
            for neighbor, weight in graph.nodes[node]:
                if neighbor not in camefrom:
                    heappush(heap, (cost + weight, neighbor, node))

对于您的示例图表，这将返回 ['A', 'B', 'C', 'I']。