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

存储它们的一种合理方法是使用从 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]]