Find the center of a sparse chart

Question

I am currently working on the following problem: for a given graph G = (V, E), I use the Dijkstra Algorithm to find the shortest distance d _i for each node v _i ∈ V from startnode v ₀ .

Now I want to find node * v ** for which the sum of all nodes of the shortest distances Σd _i from this node is minimized.

In the following example, startnode v ₀ is yellow and obviously has a distance of 0. The shortest distances are given for all other nodes.

In the first figure (the initial level in the lower left corner), the sum of all shortest distances is

Σd _i = 1 + 2 + 2 + 2 + 3 + 3 + 3 = 16

In the second figure (starting number in the middle), the sum of all shortest distances is

Σd _i = 1 + 1 + 1 + 2 + 2 + 2 + 2 = 11

The edge-weights are floats, in the example for simplicity they are chosen equal to 1.

Honestly, I could try each node to find the minimum, but this, of course, is too slow. I can’t wait for you to hear your ideas !:-)

Answer 1

In the context of social networks, the centrality metrics that you described were identified by Sadibussi in 1966 (see here or in an unofficial link here. He is also described and recommended by Freeman here (p. 225) as a measure of decentralization). It is sometimes called range (see here ).

The first search step allows you to calculate the lengths of the shortest paths from each vertex of the graph to each other. See Accepted Answers here and here . Other methods for calculating the shortest paths using all pairs are described here .

Edit:

Since you have noticed that you are interested in an approximate solution, look at the following paper from Baswana and Kavitha. Table 1.1 summarizes the known results. For the best approximate solutions, the O (n ^ (3/2)) space is now required for a 3-stretching solution (which means that the calculated distance will be greater than the real distance, but less than 3 times the real distance). I think this is not enough for most practical purposes. There are no known APASP (All-Pairs Approximate Shortest Paths) algorithms with spatial requirements <3 and less than O (n ^ 2).

Practical solutions:

Most implementations use the hierarchy inherent in real-world road networks. See for example this , this and this .