algorithmgraphlowest-common-ancestor

Distance between two nodes in a tree weighted


My Question is very straight forward.

A weighted tree is given. We must find the distance between two given nodes.

since number of queries are very high(around 75000) each time bfs be timed out so I tried different way to do that.

My algorithm is like this :

But I am not getting correct verdict as expected.Is my algorithm correct or am I missing something crucial.Guidance needed :)

P.s Incase anyone wants to see my implementation-Link http://paste.ubuntu.com/13129038/


Solution

  • Your approach sounds reasonable, but looking at the linked code I suggest you try a small example (e.g. with 3 nodes in the tree) and check the contents of the parent array carefully.

    As far as I can see, the only lines changing the contents of the parent array are:

    memset(parent,-1,sizeof parent);
    

    and

    parent[i][j]=parent[i-1][parent[i-1][j]]
    

    so I believe the contents of parent will always equal -1.

    Perhaps you need a base case setting parent[0][j] equal to the parent of j?

    Also, it is not quite clear from the code whether you are using depth to mean a count of the number of edges, or a sum of the weights of all the edges. For the distance calculation to work you need a sum of weights, but for the LCA algorithm to work you may find you need to use the count of edges.