algorithm - 在加权树中查找和存储所有对距离的最佳方法是什么？

Question

在加权树中查找和存储所有对距离的最佳方法是什么？

我目前的做法是在每个节点上运行 bfs。但很明显，这种方法存在很大的复杂性。我们可以进一步改进它吗？

Answer 1

存储它们的合理方法是使用从 0 开始的连续节点编号，这样距离就可以整齐地放在三角形数组中 d[i,j]其中 j < i .计算它们的合理方法是增加单个搜索。我将使用简写 D[i,j]对于 d[max(i,j), min(i,j)] .为了方便起见，这让我忽略了顶点编号。

Let C be a set of completed nodes
Set W be a working set of nodes
Choose any node. Add it to C. Add all its adjacent nodes to W.
while W is not empty
  Remove any node x from W
  Let e be the unique edge (x,y) where y \in C and d(x, y) be its length
  D[x, y] = d(x, y)
  for each node z in C - {y}
    D[x, z] = D[x, y] + D[y, z]
  add x to C
  add all nodes adjacent to x but not in C to W

循环不变量是 C 中的每对节点-- 调用这样的一对 (p, q) -- 我们已经计算出 D[p,q] . C 中的节点总是对应于一个子树和W与该子树相邻的节点。

虽然这与执行 n 具有相同的渐近复杂性广度优先搜索，它可能会快很多，因为它只遍历每个图边一次而不是 n次并计算每个距离一次而不是两次。

一个快速的 Python 实现:

def distance_matrix(graph):
  adj, dist = graph
  result = [ [0 for j in range(i)] for i in range(len(adj)) ]
  c = set([0])
  w = set([(x, 0) for x in adj[0]])
  while w:
    x, y = pair = w.pop()
    d = result[max(pair)][min(pair)] = dist[pair]
    for z in c:
      if z != y:
        result[max(x,z)][min(x,z)] = d + result[max(y,z)][min(y,z)]
    c.add(x)
    for a in adj[x]:
      if a not in c:
        w.add((a, x))
  return result

def to_graph(tree):
  adj = [ set() for i in range(len(tree)) ]
  dist = {}
  for (parent, child_pairs) in tree:
    for (edge_len, child) in child_pairs:
      adj[child].add(parent)
      adj[parent].add(child)
      dist[(parent, child)] = edge_len
      dist[(child, parent)] = edge_len
  return (adj, dist)

def main():
  tree = (
    (0, ((12, 1), (7, 2), (9, 3))),
    (1, ((5, 4), (19, 5))),
    (2, ()),
    (3, ((31, 6),)),
    (4, ((27, 7), (15, 8))),
    (5, ()),
    (6, ((23, 9), (11, 10))),
    (7, ()),
    (8, ()),
    (9, ()),
    (10, ()))
  graph = to_graph(tree)
  print distance_matrix(graph)

输出(带 pprint):

[[],
 [12],
 [7, 19],
 [9, 21, 16],
 [17, 5, 24, 26],
 [31, 19, 38, 40, 24],
 [40, 52, 47, 31, 57, 71],
 [44, 32, 51, 53, 27, 51, 84],
 [32, 20, 39, 41, 15, 39, 72, 42],
 [63, 75, 70, 54, 80, 94, 23, 107, 95],
 [51, 63, 58, 42, 68, 82, 11, 95, 83, 34]]