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

Question

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
            //currentVertex becomes lastVisitedVertex            
            call allVertexPairSum(weightedGraph, adjacencyList, neighbourVert, visitedSet, currentVertex)
        }
    }
}

Here is an example:

Answer 1

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.