寻找图的半径

Question

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

使用Floyd-Marshall算法找到图的直径,我想知道我在上述算法中使用的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,您有作为弗洛伊德-沃肖尔的结果.