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 0N-1 then
find i such that [ SUM d(i, j ){0=jN}] /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=jN})/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.
