Graph Theory: Find the Jordan center?

Question

I'm trying to find the set of vertices that minimizes their distance to other vertices on a weighted graph. Based on a cursory wikipedia search, I think that this is called the Jordan Center. What are some good algorithms for finding it?

Right now, my plan is to get a list of the weight for each branch emanating from a given vertex. The vertices whose weights have the smallest relative difference will be the central ones. Any other ideas?

I'm using Java, but helpful answers don't necessarily need to be Java specific.

Walther

Answer 1

I woluld first use Dijkstra algorithm (it has to be run for each verticle) for computng shortest distances between all pairs of verticles - there are also some more efficient algorithms for that like Floyd-Warshall. Then for each verticle V you have to find Vm - the largest distance to any other verticles amongs the data retuirned form Dijkstra algorithm. Then, the verticles with the smallest Vm are the one in the graph center. Pseudocode:

int n = number of verticles;
int[][] D = RunDijkstraOrWarshall()
// D[a,b] = length of shortest path from a to b
int[] Vm = new int[n];
for(int i=0; i<n i++)
{
   Vm[i] = 0
   for(int j=0; j<n; j++) 
   {
     if (Vm[i] < D[i,j]) Vm[i] = D[i,j];
   }  
}

minVm = int.Max;
for(int i=0; i<n ;i++)
{
  if (minVm < Vm[i]) minVm = Vm[i];
}

for(int i=0; i<n ;i++)
{
  if (Vm[i] == minVm)
  {
     // graph center contans i
  }

}

Brownedoff

I believe you mean to check "if (Vm[i] < D[i, j]) Vm[i] = D[i, j])". The way you have it, Vm[i] will always be zero. You want to check "if the distance from i to j is greater than the max distance from i to some other vertex that I have seen so far... change the max distance so for to the distance from i to j". – Tradition

Other than that change you need to make... good explanation :-). The code can be cleaned up a bit, but it does a good job of illustrating the concept and explaining what you wrote in words :-). +1. – Tradition

Thanks for spotting that, I've just made the correction. The above algorithm could be incorporarted right into Dijksta, or Floyd-Warshal to avoid running extra for loops (Dijkstra has to iterate through verticles anyway). – Brownedoff

Answer 2

Three algorithms for graph center problem are presented in this MSc thesis: A distributed algorithm for the graph center problem.

Tachometer

Answer 3

Starting from JGraphT version 1.1.0, you can simply use the method GraphMeasurer.getGraphCenter(). The underlying code uses a shortest path method. The user can choose which method to use, depending on some characteristics of the graph (e.g. sparse/dense/...).

Dillion