Graph Magics

Partners

DocsPal
Free online file Converter and Viewer

Graph Median

Task:

Given a connected graph. Find the vertex for which the sum of lengths of shortest paths to all other vertices is the smallest. This vertex is called median of the graph.

Solution:

The solution is straight-forward: find the lengths of shortest paths between every pair of vertices, and then for each vertex find the sum of lengths of shortest paths to all other vertices. Median of the graph is the vertex for which this sum is minimal.
Floyd-Warshall algorithm may be used to find the lengths of shortest paths between every pair of vertices, and the rest is trivial.

Algorithm:

For each pair of vertices find the length of the shortest path between them.
Find vertex i such that the sum of lengths of shortest paths to all other vertices is the smallest among all vertices.
Output vertex i found at point 2.

Pseudocode:

# N - number of vertices
# A(i,j) - length of the shortest path from vertex i to j
Compute all elements of A (by the help of Floyd-Warshall algorithm)

# sum(i) - sum of lengths of shortest paths from i to all other vertices
For i = 1 to N
    sum(i) = 0
    For j = 1 to N
        If i != j Then sum(i) = sum(i) + A(i,j)
End For i

median = 1
For i = 1 to N
    If sum(i) < sum(median) Then median = i

Output median

Complexity:

Complexity of this algorithm is determined by the part that finds the lengths of shortest paths between every pair of vertices.
Thus its complexity is O(N³).

Applications:

A warehouse should be placed in a city (a region) so that the sum of shortest distances to all other points (regions) is minimal. This is useful for lowering the cost of transporting goods from a warehouase to clients.
Same thing can be considered for selecting the place of a shop, market, office and other buildings.

Suppose that a new supermarket is going to be constructed in this area. The best location would be of course the region that is most accessible to people. A good way of finding such a region is by running Graph Median algorithm on selected vertices (regions).

Legend:
- vertex colored in dark-red represents the median of the graph
- number written on a vertex represents the length of the shortest path from median to that vertex
- number written on median represents the sum of lengths of shortest paths to all other vertices