1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 4 '17 at 3:00
  • $\begingroup$ We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Dec 4 '17 at 3:37
3
$\begingroup$

you can use Floyd Warshall algorithm to find distance of every pair and then just use a simple for to find the sum of distance of any of vertices and print the minimum of them

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.