algorithm - 最小直径生成树的算法

Question

给定一个无向连通图 G，找到一棵直径最小的生成树。

Answer 1

singhsumi 链接了 Hassin和 Tamir的相关论文，题为“关于最小直径生成树问题”，但他的答案目前已被删除。该论文的主要思想是，在无向图中找到最小直径生成树可以通过找到图的“绝对 1 中心”并返回以该处为根的最短路径树来完成。

绝对 1 中心是顶点或边上的点，从该点到最远顶点的距离最小。这可以通过 Kariv 和 Hakimi 的算法（网络定位问题的一种算法方法。I：p 中心）或 Hakimi、Schmeichel 和 Pierce 的早期算法（关于网络中的 p 中心）找到，我将尝试仅从运行时间和数十年的后见之明进行重构。（愚蠢的收费墙。）

使用 Floyd--Warshall 或 Johnson 算法计算所有对的距离。对于每条边 u--v，找到该边上 1 中心的最佳候选者，如下所示。

让边缘 u--v 上的点由 µ 索引，范围从 0（u 本身）到 len(u--v)（v 本身）。从索引 µ 处的点到顶点 w 的距离为

min(µ + d(u, w), len(u--v) - µ + d(v, w))。

作为 µ 的函数，这个数量先增加然后减少，最大值在

µ = (len(u--v) + d(v, w) - d(u, w))/2。

按此 argmax 对顶点进行排序。对于数组的每个分区到一个左子数组和一个右子数组，计算 μ 的区间 [a, b] 导致相同的 argmax 分区。将此区间与 [0, len(u--v)] 相交；如果路口是空的，那么继续前进。否则，求左子数组与 u--v 上由 a 索引的点的最大距离 L，以及右子数组与 u--v 上由 b 索引的点的最大距离 R。（计算这些最大值的成本可以通过在开始时从左到右和从右到左扫描来分摊到每个分区的 O(1)。）最好的选择是 [a, b] 中的 µ最小化 max(L - (µ - a), R + (b - µ))。