Sum of all distances in connected DAG in $O(n\log n)$

Question

I have a DAG with $n$ nodes and $n-1$ edges. The edges in DAG (fixed) are defined as follows: For every node $i$, $1 \le i \le n-1$ is connected to node $i+1$. The lengths of the $n-1$ edges are given as input.

I need to compute the sum of all of the distances between all pairs of different vertices, i.e., to compute $\sum_{u<v} d(u,v)$, which is the sum of the distances for each pair $u,v$ such that $u<v$.

For example, suppose $n=4$, and the edge lengths are $1,1,1,1$. Then the pairs along with their distance would be $(1,2):1,(1,3):2,(1,4):3,(2,3):1,(2,4):2,(3,4):1$, so the total sum of distances would be $1+2+3+1+2+1=10$.

I tried Dijkstra's Algorithm (time complexity $O(n\log n)$) on every node but the time complexity is $O(n^2 \log n)$ which is inefficient. Is there a way to reduce it to $O(n \log n)$ or less?

Answer 1

I think the question is not clear enough, but what I understood is that we want to find the sum of all the shortest path from $u$ to $v$ such that $u < v$. The trick is that the graph is actually a directed chain, so we can represent the edges in an array $A$ of length $n - 1$.

The brute force formula is $\sum_{i=1}^{n -1} \sum_{j=i + 1}^{n} \delta(i,j)$. Where $\delta(i,j)$ is the shortest path from $i$ to $j$, because our graph is a chain, we can simply express this as $\delta(i,j) = \sum_{k=i}^{j - 1} A_{k}$. In the example you provided with 4 nodes $A =[1,1,1]$. The above formulas have a complexity of $\Theta(n^3)$, which can be improved to $\Theta(n^2)$ by doing a prefix sum on $A$. But a pattern can easily detected by looking carefully where the items of $A$ repeat.

For example, if $A = [1,2,3]$ the above formulas would provide the following operations:

$(1 + (1+2) + (1+2+3)) + (2 + (2+3)) + (3)$, here each "big parenthesis" is the computation from each node. The last node is obviously ignored.

We can rewrite this as:

$3 *(3 * 1) + 2 *(2 * 2) + 1 * (1 * 3)$

For example $3 *(3 * 1)$ means that $3$ was repeated once ($1$) on $3$ parenthesis. Likewise, $ 2 *(2 * 2)$ means that $2$ is repeated two times on $2$ parenthesis and so on.

The repetitions have a pattern: the number of times it appears on a "big parenthesis" is actually the index of the element, but the number of times is repeated inside the parenthesis decreases as the index increases because less paths starts from nodes that are closer to the end of the chain. Work through the example and you will find the pattern, make sure you understand this paragraph.

As you mentioned that you have not found the pattern, the above discussion can be summarized in this formula: $\sum_{i=1}^{n - 1} A_{i} * i * (n - i)$. Remember that $n$ is equal to the number of nodes and $A$ contains the edges, which are $n - 1$.

The proof of the above intuition is left as an exercise for the reader :-).

EDIT: Just in case, the complexity is $\Theta(n)$ because we only do a loop to compute the summation and the inner operations are $\Theta(1)$. Depending on how you represent the graph in the input, the memory complexity can be either $\Theta(1)$ or $\Theta(n)$.

Answer 2

From the comments it seems you're interested in the sum of the distances between all pairs.

As in your comment, let $a_i$ be the weight of the edge between node $i$ and node $i+1$. The weight of the path between node $i$ and node $j$ is $a_i+\cdots+a_j$. Using this, it is easy to calculate the answer for small $n$:

• $n=2$: $a_1$
• $n=3$: $a_1+(a_1+a_2)+a_2 = 2a_1+2a_2$
• $n=4$: $a_1+(a_1+a_2)+(a_1+a_2+a_3)+a_2+(a_2+a_3)+a_3 = 3a_1+4a_2+3a_3$
• $n=5$: $4a_1+6a_2+6a_3+4a_4$
• $n=6$: $5a_1+8a_2+9a_3+8a_4+5a_1$

And so on. Let's put these numbers in a table (we'll stop at the middle of each coefficient vector): $$ \begin{array}{ccccc} 1 \\ 2 \\ 3 & 4 \\ 4 & 6 \\ 5 & 8 & 9 \\ 6 & 10 & 12 \\ 7 & 12 & 15 & 16 \\ 8 & 14 & 18 & 20 \\ 9 & 16 & 21 & 24 & 25 \\ 10 & 18 & 24 & 28 & 30 \end{array} $$ The pattern is reasonably obvious to spot.

For the proof, you have to calculate in how many shortest paths does the edge between node $i$ and node $i+1$ participates — this is the coefficient of $a_i$.

All details left to you.