# Finding optimum point that minimizes maximum distance

Does anyone know how I should approach this algorithm? It needs to have $$O(n^3)$$ complexity and I can only come up with an algorithm that has $$O(n^4)$$ complexity (of doing a n^2 min path from each vertex to $$n-1$$ other vertexes, and since I need to do this n times, it will be $$n^4$$ or so I think...

Input: Array $$A[1...n][1...n]$$ such that $$A[i][j]$$ gives length of edge(distance) between two points or $$-1$$ if there isn't and edge.

Output: a vertex $$v$$, such that distances(total lengths) to all other vertexes are minimized.

Can someone explain in pseudocode or in words how to do this?

• compute all pair shortest path distances, and update the distance matrix. This operation takes $O(n^3)$ using Floyd Warshall algorithm. Now with the updated distance matrix, sum the values along each column (row) and then choose the index with the least sum. Dec 4 '17 at 3:00