这个理论叫 **最小半径生成树Minimum Radius Spanning Tree, MRST的核心定理没有特别花哨的名字但可以用一句话概括“图的最小半径生成树的半径 图的半径且最短路径树就是最优解。”定理的正式表述给定一个无向连通图 G(V,E)G(V,E)带非负边权定义图的半径r(G)min⁡v∈Vmax⁡u∈VdG(v,u)r(G)minv∈V​maxu∈V​dG​(v,u)找个中心点到所有点最远距离最小。任意生成树 TT 的半径 r(T)≥r(G)r(T)≥r(G)。存在一棵生成树 T∗T∗ 使得 r(T∗)r(G)r(T∗)r(G)这棵树就是以图中心为根的最短路径树。它依赖的底层理论这个定理由两部分支撑① 最短路径树Shortest Path Tree, SPT从某个源点 ss 跑 Dijkstra/BFS记录每个点的前驱得到一棵树。在这棵树中根到任意点的距离 原图中 ss 到该点的最短距离。所以如果 ss 选的是图的中心 cc那么这棵树的半径 cc 的离心率 图的半径。② 下界证明任何生成树不可能更小对任意生成树 TT任取树中一点 xx 作为中心TT 中 xx 到所有点的距离 ≥ 原图中 xx 到所有点的最短距离因为原图边更多路径更短。所以 r(T)≥min⁡vmax⁡udG(v,u)r(G)r(T)≥minv​maxu​dG​(v,u)r(G)。这个定理在算法竞赛中叫什么中文圈常叫它“最小半径生成树 图半径 最短路径树”没有专用人名。英文教材里归在“Spanning Trees and Network Center”章节属于图论中“中心与生成树”的基础结论。和它容易混淆的是最小直径生成树MDST那个复杂很多要用绝对中心而最小半径生成树简单得多就是最短路径树。为什么你刚才的暴力枚举和这个定理一致暴力枚举是在所有生成树里找最小半径。定理告诉你不用找直接找图的中心然后以它建最短路径树这棵树就是所有生成树里半径最小的那一批。所以枚举的结果必然等于定理算出来的值你那个例子里都是 1。你如果还想深入我可以给你证明的完整数学推导或者对比“最小直径生成树”的区别围绕“生成树的最小半径”这个点往外延伸还有4 个极易混淆的“亲戚”理论和算法。我帮你梳理一下以后面试或做题看到它们就不会懵了1. 最小直径生成树MDSTMinimum Diameter Spanning Tree这是和你问的MRST最小半径最像、但难度天差地别的兄弟。区别MRST 看的是“根到最远叶子”单源最远MDST 看的是“树上最远的两个点”任意两点最远即直径。关键定理图的绝对 1-中心。MRST 的中心必须是顶点比如节点 3但 MDST 的最优中心可以落在边的内部。例子一条长度为 10 的边连接 1 和 2。MRST 选顶点 1 或 2半径 10但 MDST 可以把中心选在边中点直径 10半径5。计算 MDST 需要复杂的“绝对中心”算法不能简单套最短路径树。2. 最小生成树MSTMinimum Spanning Tree vs 最小瓶颈生成树MBST这是按边权总和/最大值来划分的和“距离”维度不同MST最小生成树目标是让所有边权之和最小如 Kruskal/Prim 算法。MBST最小瓶颈生成树目标是让生成树中最大的单条边权最小。注意MST 自动是 MBST但 MBST 不一定是 MST。它们和“半径/直径”没有直接关系因为权重小不代表点间距离近可能绕远路。3. 图论中的“绝对中心”Absolute 1-Center这个是你解题的底层工具定义在一个图里找一个点不一定是顶点可以在边上使得它到所有顶点的最远距离最小。如果你把中心限制在顶点上叫“顶点中心”如果能放在边上叫“绝对中心”。你的 MRST 问题只用到“顶点中心”所以直接 Floyd 算离心率就行。但如果遇到 MDST就必须用二分答案 区间交集去求“绝对中心”。4. k-中心问题k-Center Problem这是你问的“单中心”的高维扩展问题选 kk 个中心点比如建 kk 个消防站让所有点到最近中心的最大距离最小。在生成树场景下就是求“最小半径的 k-树覆盖”。这个问题在普通图上是NP-难的没有多项式精确解只能用贪心近似2-近似算法。一句话帮你分清防混淆口诀求总权重最小→MSTKruskal/Prim求边最大值最小→MBSTMST 自动满足求单源最远距离最小中心是顶点→MRST你的问题最短路径树搞定求任意两点最远距离最小中心可在边上→MDST需绝对中心算法复杂