I think if we calculate the center of the graph that will give the solution, to do that 1. find the eccentricity of every node using all pair shortest path algo's ( Floyd warshall). 2. The node which is having min eccentricity is your P.
On Wed, Apr 25, 2012 at 6:14 PM, Navneet <navneetn...@gmail.com> wrote: > 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- VISU.... Airvana, R&D Engineer -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
