为无向图中的所有节点存储 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)

变量说明：

adj[cur_nod]包含节点cur_nod
siz[cur_nod]（不是int数据类型的列表）包含从节点1到节点的所有距离 cur_nod
w(x,y)表示连接节点x和y的边的权重
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 .

那么 siz = [[-1], [0], [1], [3], [4]]。（请注意，我最初设置了 siz[1]=0 和 siz[0]=-1，因为我的起始节点是 1 并且数组是 0 索引但我需要它作为 1 索引）而理想的 siz 应该有已经 [[-1], [0], [1], [3,9], [4,8]]

Answer 1

您可以做的只是简单地考虑您正在穿越的当前路径。对于上次访问的节点，创建相应的新路径并将其添加到我重命名为node_paths的'siz'。然后对每个邻居进行递归。

因为给 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 的一个很好的属性是（给定二进制表示）您采用的任何组合（在数字中）将产生不同的总和，"uniquely" 描述了您的路径（即使在那里我们也有路径可供使用）
我没有遵循你的算法精神，因为我认为它对于像上面那样的菱形图是失败的（即使有向图中没有循环）（因为我们可能会累积相同的路径）（但我只是猜到了，没有测试猜测，可能是错误的）

为无向图中的所有节点存储 dist(node, start) 的算法

Algoriithm to store dist(node, start) for all nodes in an undirected graph

python

algorithm

graph

graph-algorithm