CODEWITHSUNDEEP
algorithmgraphtree
Karan Nagpal
Karan Nagpal

Reputation: 51

Distance of every possible path between all nodes in minimum spanning tree

I want to get distance of all nodes from all nodes. There are a few questions regarding this but none solves my problem. What my appoach is that I am implementing recursive DFS and storing the result of each path while backtracking but the problem is I am having high running time and I a going through a path N number of times (N being the number of edges).

As you can see in my code I am running dfs for every possible node as a root. I dont know how to reuse the path to know the answer just in One Iteration of DFS search.

I think it could be done in O(n) as its a minimum spanning tree and there is only one path between a pair of nodes.

my code :

vector<int> visited(50001);
map< pair<ll,ll> , ll> mymap;
map<ll, vector<ll> > graph;

void calc(ll start,ll node)
{
    visited[node]=1;
    vector<ll>::iterator it;
    for (it = graph[node].begin(); it != graph[node].end(); ++it)
    {
        if (!visited[*it])
        {
            ans+=mymap[make_pair(node,*it)];
            mymap[make_pair(start,*it)]=ans;
            calc(start, *it);
            ans-=mymap[make_pair(node,*it)];
        }
    }
}

In main :

for(i=1;i<=n;i++)
    {
        fill(visited.begin(),visited.end(),0);
        ans=0;
        calc(i,i);
    }

Upvotes: 1

Views: 2179

Answers (1)

halfo
halfo

Reputation: 223

I can think of a solution of complexity O(n * logn) using divide and conquer. Let me share it.

Let's choose an edge e of distance d which is connecting node a and b. Let's cut it. Now we have two tree with root a and b. Let's assume,

  • number of nodes in tree a = na
  • sum of distance between every node in tree a is = ca
  • sum of distance of every node to root in tree a is = ra
  • number of nodes in tree b = nb
  • sum of distance between every node in tree b is = cb
  • sum of distance of every node to root in tree b is = rb

So the distance between every node in the original tree is: ca + cb + (nb * ra + na * d * nb + na * rb))

Now, we can calculate the sum of distance of every node in tree a or b using same approach. One thing to be careful is that, we have to choose such edge e such that the difference between the number of components isn't much. You can always find an edge in a tree that if you cut that edge, the difference between the number of nodes in resulting two trees won't be more than 1.

Upvotes: 1

Related Questions