3
$\begingroup$

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: Example Tree

$\endgroup$
  • 2
    $\begingroup$ I don’t understand the problem definition. What is an “edge pair”? $\endgroup$ – Yuval Filmus Jun 24 at 15:40
  • 3
    $\begingroup$ Also, this is not a programming site, so please replace Java with pseudocode. $\endgroup$ – Yuval Filmus Jun 24 at 15:40
  • $\begingroup$ Your question might have been asked before. $\endgroup$ – Yuval Filmus Jun 24 at 15:41
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Jun 24 at 16:05
  • $\begingroup$ @YuvalFilmus - edited as per comments. please share the link if asked before $\endgroup$ – Aravind Sharma Jun 24 at 17:34
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.