We cannot do it without computing distances of each node from all other nodes. So to begin with, construct a matrix representation of the graph with distances filled in for every pair of points.
Proceed to calculate the minimum spanning tree of such a weighted graph. Kruskal's and Prim's are two well known algorithms to do that. Such a point should lie on this spanning tree. Not very sure how to quickly find the desired point on MST, but problem becomes easier with MST. On Wednesday, 25 April 2012 11:10:38 UTC+5:30, tech coder wrote: > > Given N points(in 2D) with x and y coordinates. You have to find a > point P (in N given points) such that the sum of distances from > other(N-1) points to P is minimum. > > -- > > Regards > "The Coder" > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/rJZk24xBTqYJ. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
