考虑我们有一个加权无向图，其中对于任何两个顶点，都有一条连接它们的唯一路径。有 n 个顶点和 n - 1 条边，每条路的成本是 c_i。
现在，如果连接两个给定顶点的每条路径都有一定的成本，这取决于它经过的道路，我们如何才能有效地计算所有城市对之间的总成本？
例如，每条路径的代价可以是它经过的第一条路和最后一条路的总和，也可以是它经过的每条路的代价的某次幂之和，也可以是代价的最大值减去它经过的道路成本的最小值:任何取决于道路成本的公式。
要使用什么算法才能有效地解决问题？
最佳答案
对于任何路径 p，让 max(p) 和 min(p) 表示它经过的道路的最大和最小成本经过。
然后 Total_cost = sum for all path p [max(p) - min(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
每次插入边 e 时，它都会连接两个组件 S，T，您可以看到对于来自的每条路径 p S 到 T，max(p) = cost(e)
因此，您可以通过对它们求和来找到所有路径 p max(p) 的 sum。
要有效地连接两个组件，我认为您可以使用 Kruskal 算法的思想。
同样，您可以找到所有路径 p min(p) 的总和，最后是总成本。
关于algorithm - 加权无向图中的总成对成本，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41652332/