加权无向图中的总成对代价

Question

假设我们有一个加权无向图，其中，对于任意两个顶点，都有一条唯一的路径连接它们。有n个顶点和1个边，每条路的成本是c\u i。

现在，如果连接两个给定顶点的每条路径都有一定的成本，这取决于它所经过的道路，那么我们如何有效地计算所有城市对之间的总成本？

例如，每条道路的成本可以是它经过的第一条道路和最后一条道路的总和，或者是它经过的每条道路的成本的某些幂的总和，或者是成本的最大值减去它经过的道路的最小值：任何取决于道路成本的公式。

为了有效地解决问题，应该使用什么算法？

Answer 1

对于图形中的每条边，通过“删除”它，可以得到两个断开连接的组件，分别是u和v。

这意味着，边是原始图形中从u中的每个节点到v中的每个节点的路径的一部分，并且存在这样的路径<这意味着，问题归结为计算这些集合的大小。

一种方法是选择任意顶点，并通过使所有边都指向外部，使其成为根。这样做之后，你就有了一棵有根的定向树。

通过在线性时间内遍历树一次，现在可以找到每个子树的大小：

size(u) = sum { size(v} | v is a child of u}  + 1

计算完所有子树的大小后，对于每个有向边（u， v），原始集|V|和|U|的大小是size（v）和n-size（v）。

遵循这些步骤可以得到线性时间延迟，并使用以下高级伪代码。

Choose arbitrary r
Calculate size(u) for all nodes
sum = 0
for each edge (u,v) do:
  sum = sum + (cost(u,v) * (size(v) * (n-size(v))))
return sum

Answer 2

对于任何路径，让最大（p）和最小（p）表示其所经过道路的最大和最小成本。然后Total\u cost=所有路径p的总和[最大（p）-最小（p）]

然后，可以通过以下方式找到所有路径p max（p）的总和

Let G=(V,E) be the input graph, which should be a tree
Create a graph G' with vertices set V and no edges
Insert every edge in E to G' from lowest cost to hightest cost

每次插入一条边时，它将连接两个组件S、T，您可以看到，对于从S到T的每条路径，最大值（p）=成本（e），所以您可以通过求和来找到所有路径p最大值（p）的总和。为了有效地连接两个组件，我认为可以使用Kruskal算法的思想。

同样，您可以找到所有路径p min（p）的总和，最后是总成本。