1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @YuvalFilmus I have been trying to find it since last week and that's why I asked for the help. Can you please help me out ? $\endgroup$ – Sam Thornton Mar 13 '17 at 8:08
  • $\begingroup$ There are simple formulas for this sum. Try solving the cases $n=2,3,4$ first, and then generalize. Note that there is absolutely no need to run Dijkstra's algorithm, since as you mention, the distance between two vertices is the sum of weights of the path connecting them. $\endgroup$ – Yuval Filmus Mar 13 '17 at 8:10
  • $\begingroup$ @YuvalFilmus Assuming the weight between node$i,i+1=a_i$. Then for $n=2$ nodes ,dist=$ a_1$, for $n=3$ nodes dist= $a_1+(a_1+a_2)+a_2$, for $n=4$ nodes dist = $a_1+(a_1+a_2)+(a_1+a_2+a_3)+(a_2)+(a_2+a_3)+a_3$. I thought the pattern would $(n-1)*$sum of all $a_i$ but it's not correct. Can you help in correcting the formula please ? $\endgroup$ – Sam Thornton Mar 13 '17 at 8:56
  • $\begingroup$ I don't think you need my help. You need to spend a few hours on it. $\endgroup$ – Yuval Filmus Mar 13 '17 at 8:57
  • $\begingroup$ math.stackexchange.com/q/2184471/14578 $\endgroup$ – D.W. Jun 16 '17 at 21:26
1
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

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.

$\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.