+-
图形G的半径由图形中节点的最小偏心率定义。为了解决这个问题，我需要哪种算法？
使用Floyd-Warshall算法查找图的直径，我想知道我在所述算法中使用的n * n距离数组是否也可以用于查找半径。
6
投票
投票
是的，可以。对于每个顶点，通过找到从顶点到任何其他节点的最大距离来找到其离心率，然后从这些顶点中选择最小值以获取半径。
伪代码：
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之间的距离。
