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

//Adjacency List
adjacencyList: array of linked list

//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
visitedSet: LinkedHashSet of Size N
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
}

add currentVertex to visitedSet

for each neighbourVert in adjacencyList[currentVertex] {
if(neighbourVert not equals lastVisitedVertex) {
//neighbourVert becomes currentVertex
//cur

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.

StackExchange Computer Science Q#111109, answer score: 2