CODEWITHSUNDEEP
algorithmgraph
maregor
maregor

Reputation: 797

Finding radius of graph

The radius of a graph G is defined by the minimum eccentricity of the nodes in the graph. What kind of algorithm do I need in order to solve this?

Using the Floyd-Warshall algorithm to find the diameter of a graph, I'm wondering if the n*n array of distances that I used in the said algorithm can also be used to find the radius.

Upvotes: 3

Views: 3247

Answers (1)

amit
amit

Reputation: 178441

Yes, it could. For each vertex, find its eccentricity by finding the maximal distance from it to any other node, and choose the minimal out of these, to get the radius.

Pseudo Code:

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

In the above, d(v,u) is the distance between v to u, that you have as a result of Floyd-Warshall.

Upvotes: 8

Related Questions