use All Pair Shortest Path
On Oct 6, 11:11 am, Nitin Nizhawan <nitin.nizha...@gmail.com> wrote:
> hi,
>
> given a tree with N nodes find the node such that its average total
> distance from each other node is smallest
>
> i.e. if nodes are labeled 0....N-1 then
> find i such that [ SUM d(i, j ){0<=j<N}] /N is minimum
>
> NOTE: This is different from the classic problem of finding tree center
> where tree center is the node such that its maximum distance to other nodes
> is minmum
>
> this must be done is O(n) time and O(n) space
>
> sample input : an integer array Tree with N elements where each element
> T[a]=b represents an edge (a,b) when a!=b
>
> Tree[]={14,9,11,16,14,0,11,6,14,11,3 ,16,13,17,12, 1, 5,17}
>
> correct answer is 16.
>
> My solution was to find (SUM(i,j) {0<=j<N})/N for any one value of i using
> dfs then find it for other is value of i's by the fact that if there is an
> edge in tree (a,b)
> and average total distance for node a is X and then average total distance
> for node be can be found in constant time as follows
>
> if we remove the edge (a,b) from the tree then there will be two connected
> components in the tree one that contains node a and other that contains node
> b.
> Let number of nodes in first be Na and number of nodes in second be Nb
> then average total distance of node b is = X + Na - Nb. Na, and Nb can
> be found in linear time again using dfs for each node.
>
> Somehow this solution gives wrong answer ,
>
> Any Help ?????
--
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.
