1
$\begingroup$

I came across this problem in an online judge: We are given a distance matrix consisting of $N$ rows and columns. The $i$th line of $j$th row is the distance between node $i$ and $j$ (not necessarily neighbors). The task is to find out if there exists a tree satisfying the given distance matrix or not. The only constraint is $1 \le N \le 2000$ and the time limit is 1 second.

Some sample test cases for clarity:

Input:
N = 3
0 2 7
2 0 9
7 9 0
Output:
True

Input:
N = 3
0 1 1
1 0 1
1 1 0
Output:
False

I couldn't find an answer that is feasible for implementing in a short period of time (this is kind of important for me as I participate in competitions sometimes). An idea came to my mind is that to take the distance matrix as it was an adjacency matrix and compute MST, and then run Dijkstra's SSSP from each vertex through this MST and generate a new distance matrix and finally compare if the initial distance matrix and the matrix we found are identical. I know that this solution is not efficient nor logical (and also I'm not sure if this would work correctly) and that's why I'm posting here for an answer. I can tell that the solution involves DSU (Disjoint Set Union) and DFS from the problem tags but it just didn't come to my mind.

$\endgroup$
  • $\begingroup$ There may be many graphs corresponding to a specific distance matrix. For your first example, the triangle graph with distances of the three edges 2, 7, 9 also satisfies your distance matrix, but it is not a tree. Does the problem ask whether there exists a tree satisfying the given distance matrix? $\endgroup$ – xskxzr Nov 10 '18 at 12:33
  • $\begingroup$ You are correct. It asks whether there exists a tree satisfying the given distance matrix or not. $\endgroup$ – Mehmet Eren Aldemir Nov 10 '18 at 12:37
  • $\begingroup$ Are negative distances allowed? $\endgroup$ – xskxzr Nov 10 '18 at 12:42
  • $\begingroup$ No. All the weights are non-negative. $\endgroup$ – Mehmet Eren Aldemir Nov 10 '18 at 12:45
  • 1
    $\begingroup$ Related, actually constructing the tree: Is it possible to reconstruct graph if we have given matrix of shortest pairs. $\endgroup$ – Hendrik Jan Nov 10 '18 at 14:06
0
$\begingroup$

We can assume all weights are positive. Otherwise we can merge all pairs of nodes with distance $0$ to get an equivalent new distance matrix (a rigorous proof would be a little verbose here so I omit it).


We can process all distances from small to large. For a distance $d$ between node $u$ and node $v$, check if $u$ and $v$ are connected (initially there is no edge thus every pair of nodes is not connected). If they are not connected, add an edge with weight $d$ between them. Finally we will get a tree and we can check whether this tree satisfies the distance matrix.

To efficiently determine whether two nodes are connected, we can maintain a disjoint-set data structure where each disjoint set represents a connected component. With this data structure, we can build the tree in $O(N^2)$. In addition, computing all-pair distances in a tree takes $O(N^2)$ time, so the total running time is $O(N^2)$, which is sufficient for the constraints.


Correctness of the Algorithm

If the algorithm reports "yes", then we indeed build a tree satisfying the distance matrix.

On the other hand, if there is a tree $T$ satisfying the distance matrix, we claim that our algorithm will build $T$ finally. We prove this claim by mathematical induction. Suppose our algorithm processes the distances of pairs $(u_1,v_1),(u_2,v_2),\ldots$ in order. Denote by $D(u,v)$ the distance between $u$ and $v$ in the distance matrix.

  1. Our algorithm always adds the edge $(u_1,v_1)$ with weight $D(u_1,v_1)$, while there is always an edge $(u_1,v_1)$ with weight $D(u_1,v_1)$ in $T$.

  2. Assume our algorithm agrees with $T$ for pairs $(u_1,v_1),\ldots,(u_{n-1},v_{n-1})$.

    If there is an edge $(u_n,v_n)$ in $T$ (it must have weight $D(u_n,v_n)$), then $u_n$ and $v_n$ are not connected through edges $(u_1,v_1),\ldots,(u_{n-1},v_{n-1})$, which means our algorithm will add this edge by inductive assumption.

    Otherwise, there is a path connecting $u_n$ and $v_n$ with length $D(u_n,v_n)$ in $T$. All of the edges in this path must have weights less than $D(u_n,v_n)$, thus are already added by our algorithm (again, by inductive assumption) when processing $(u_n,v_n)$. This means when our algorithm processes $(u_n,v_n)$, $u_n$ and $v_n$ are already connected, thus our algorithm will not add the edge $(u_n,v_n)$.

Now we have proved our algorithm indeed builds $T$, thus will report "yes".

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