algorithm - 寻找图形的半径

Question

图 G 的半径由图中节点的最小偏心率定义。我需要什么样的算法来解决这个问题？

使用 Floyd-Warshall 算法求出图形的直径，我想知道我在上述算法中使用的 n*n 距离数组是否也可以用来求出半径。

Answer 1

是的，它可以。对于每个顶点，通过找到从它到任何其他节点的最大距离来找到它的偏心率，并从中选择最小的距离，以获得半径。

伪代码:

radius = infinity
for each vertex v:
    eccentricity = -infinity
    for each vertex u:
         eccentricity = max(eccentricity ,d(v,u))
    radius = min(radius, eccentricity )

在上面，d(v,u) 是 v 到 u 之间的距离，这是 Floyd 的结果-沃歇尔。