用于存储无向图中所有节点的dist（node，start）的算法

Question

目标是创建一个名为siz的数组，该数组存储从起始节点开始的所有路径的长度。在理想情况下，我将调用f（start）并期望siz [v]为图中的所有顶点v填充。

这是我正在使用的算法。

def f (node):
    vis[node] = 1
    for elem in adj[node]:
        if vis[elem]==0:
            for i in siz[node]:
                    siz[elem].append(i + w[(node,elem)])
            f(elem)

可变描述：

1. adj [cur_nod]包含节点cur_nod的所有邻居
2. siz [cur_nod]（这是一个不是int数据类型的列表），包含从节点1到节点的所有距离cur_nod
3. w（x，y）表示连接节点x和y的边缘的权重
4. vis [nod]跟踪是否访问了一个节点。 0代表未访问，1代表已访问。

递归似乎不正确，我不知道何时将节点实际标记为已访问。另外，由于有周期，所以我不希望距离包含周期。例如，A-> B-> C-> A-> D根本不应该是这种情况。它应该只是A-> D或所有其他方法，都可以通过A到D的路径而无需经历一个循环。

给出此算法如何无法按预期工作的示例：

如果输入节点和边权重为w（1,2）= 1，w（2,3）= 2，w（2,4）= 7和w（3,4）= 1。

Then siz = [[-1]，[0]，[1]，[3]，[4]]。 （请注意，由于起始节点为1且数组为0索引，但我最初将siz [1] = 0和siz [0] =-1设置为1，但理想的siz应该具有被[[-1]，[0]，[1]，[3,9]，[4,8]]

Answer 1

您可以做的只是考虑您正在遍历的当前路径。对于最后访问的节点，创建相应的新路径并将其添加到我重命名为siz的“ node_paths”中。然后为每个邻居递归。

由于给f的路径（请参见下面的代码）是copy，因此您不必手动删除添加的节点（但是，例如，如果您使用path.append(node)，则当您退出f时，您将不得不path.pop()）

data = [
(1, 2, 1),
(1, 3, 2),
(2, 4, 4),
(3, 4, 8),
]
adj = {}
w = {}
node_paths = {}
for (src, dst, weight) in data:
  if src not in adj:
    adj[src] = []
  if dst not in adj:
    adj[dst] = []

  adj[src].append(dst)
  adj[dst].append(src)
  w[(src, dst)] = weight
  w[(dst, src)] = weight

def f (path, weight, node, node_paths):
  if node in path:
    return
  path_to_node = path + [node]
  weight_to_node = weight + w[(path[-1], node)]
  if node not in node_paths:
    node_paths[node] = []
  node_paths[node].append((path_to_node[1:], weight_to_node))
  for neigh in adj[node]:
    f(path_to_node, weight_to_node, neigh, node_paths)

node_paths = {}
start = 1
w[(-1, start)] = 0
f([-1], 0, start, node_paths)
print(node_paths)

#{1: [([1], 0)], 2: [([1, 2], 1), ([1, 3, 4, 2], 14)], 4: [([1, 2, 4], 5), ([1, 3, 4], 10)], 3: [([1, 2, 4, 3], 13), ([1, 3], 2)]}

在上面的代码中，我同时存储了路径和加权和以简化调试，但显然您可能会丢弃存储的路径

几点：

• 调试时避免询问用户输入和硬编码的内容，有助于重现性并加快尝试的时间
• 1,2,4,8的一个不错的特性是，（采用二进制表示）您采用的任何组合（在数字中）将产生不同的总和，“唯一”地描述您的路径（即使我们只有可用的路径）
• 我没有遵循您的算法精神，因为我认为像上面的菱形图那样它会失败（即使有向图中没有循环）（因为我们可能会累积相同的路径）（但是我只是猜到了，没有测试猜，可能是错误的）