# Algorithm to compute sum of cost of all path between pair of unique vertices of a tree

Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of cost of all path between pair of unique vertices.

Thus, there are total nC2 or n(n-1)/2 such pairs. The time complexity of the mentioned algorithm is n(n-1)/2. Please suggest an algorithm with better space and time complexity if possible. Below is the pseudocode.

//Final Result
sumAllPair = 0;

//Total Number of vertices
N

//Weighted Graph Matrix
weightedGraph: two dimensional integer array N*N

//Initialize Matrix
loop ii from 0 to N-1 {
loop jj from 0 to N-1 {
if(ii equals jj) {
weightedGraph[ii][jj] = 0
}else {
weightedGraph[ii][jj] = INFINITY
}
}
}

currentVertex = 0
lastVisitedVertex = -1
call allVertexPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex)

print sumAllPair

/*
* Say graph has vertices 1,2,3,4,5,6,7
*
* allVertexPairSum() will compute sum of cost of all path between pair of unique vertices like this:
*              21 + (31+32) + (41+42+43) + (51+52+53+54) + (61+62+63+64+65)+(71+72+73+74+75+76)
*              where ij represents cost of path from vertex i to vertex j
*
* Time Complexity:
*      N(N-1)/2 or Combination(N,2)
*/
function allVertexPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex) {

for each  visitedVer in visitedSet{
cost = weightedGraph[visitedVer][lastVisitedVertex] +  weightedGraph[lastVisitedVertex][currentVertex]
sumAllPair = sumAllPair + cost
weightedGraph[visitedVer][currentVertex] = cost
weightedGraph[currentVertex][visitedVer] = cost
}

for each neighbourVert in adjacencyList[currentVertex] {
if(neighbourVert not equals lastVisitedVertex) {
//neighbourVert becomes currentVertex
//currentVertex becomes lastVisitedVertex
call allVertexPairSum(weightedGraph, adjacencyList, neighbourVert, visitedSet, currentVertex)
}
}
}


Here is an example:

• I don’t understand the problem definition. What is an “edge pair”? – Yuval Filmus Jun 24 '19 at 15:40
• Also, this is not a programming site, so please replace Java with pseudocode. – Yuval Filmus Jun 24 '19 at 15:40
• Your question might have been asked before. – Yuval Filmus Jun 24 '19 at 15:41
• I don't understand your question. What sum are you trying to compute? Maybe I could figure it out from your example but I'm not going to and I shouldn't have to. And surely your algorithm doesn't take 100+ lines to implement: please remove all the parts of that code that aren't directly related to your question, and ideally don't rely on people understanding Java. – David Richerby Jun 24 '19 at 16:05

Let's build some recursive function. We start picking any vertex of the tree $$T$$ and call it $$R$$ as root. If $$R$$ was removed, you would get a forest of several sub-trees. Every subtree $$T_k$$ has a vertex $$k$$ connected to $$R$$ in $$T$$.

Now there are 3 types of paths contributing to the sum of cost of paths $$N(R)$$:

• $$I(R)$$, the cost of all inner paths of the sub-trees (computed with recursion),
• $$S(R)$$, the cost of all paths starting on $$R$$: $$(R, i)$$ for any $$i \ne R$$,
• $$C(R)$$, the paths between the different sub-trees.

Once you recursively have computed the 3 components for each of these vertex $$k$$ in its own sub-tree $$T_k$$. Let's call $$E(k, R)$$ the cost of the edge $$(k, R)$$ and $$n_k$$, the number of vertices in $$T_k$$.

You can compute $$N(R)$$:

• $$I(R) = \sum_k N(k)$$
• $$S(R) = \sum_k S(k)+n_k E(k, R)$$,
• $$C(R) = \sum_{k1, k2, k1 \ne k2}(S(k1)+n_{k1}E(k1, R))(S(k2)+n_{k2}E(k2, R))$$

Note that if $$R$$ is connected to only one other vertex, $$C(R) = 0$$. You also can track $$n$$ with $$n_R = \sum_k n_k + 1$$.

This has a linear time and space complexity.