# Is it possible to reconstruct graph if we have given matrix of shortest pairs

I'm trying to reconstruct graph if we have given the result of floyd-warshall algorithm, more formally:

Let's say we have given undirected weighted tree (graph without cycles) with $N$ nodes, such that from this graph we only have given matrix $g$ of size $N \cdot N$ elements, such that $g(i, j)$ gives the shortest path between nodes $i$ and $j$, note that it doesn't mean that nodes $i$ and $j$ are directly connected with edge.

What I think

We can say that node $x$ belongs on the path from node $a$ to node $b$ if and only if: $g(a,b) = g(a, x) + g(x, b)$.

If we fix nodes $a$ and $b$ in $O(N \cdot N)$ and we iterate over all other nodes, we will get total complexity of $O(N^3)$.

Is it possible to reduce this complexity to $O(N^2)$.

• Well, for a start, I suggest to find shortest pairs. The shortest pair is guaranteed to be a single edge, second shortest is either a single edge or is 2-edge path that contains shortest edge. Maybe this will decrease runtime. – rus9384 Sep 8 '17 at 17:36
• Can the weights on the original tree be negative? zero? – D.W. Sep 8 '17 at 20:43
• The lengths will be positive natural numbers, there will be zero in the matrix only when we are requesting shortest path from node $i$ to node $i$. – someone12321 Sep 9 '17 at 7:42

I would suggest the following approach.

Maintain a data structure $H$ of $(i,j, g(i,j))$ triples so that you can efficiently find and remove a triple $(i,j,w)$ that minimises $w$.

Maintain a partition $P$ of nodes $V = \{1,2,\dotsc,N\}$.

Maintain a tree $T$.

We will maintain the invariant that $T$ contains some edges of the tree that we are trying to reconstruct, each part $X \in P$ is some subtree that we have not reconstructed yet. Eventually, $T$ will be the tree and $P$ will consist of singleton sets.

Initially, $P = \{V\}$ and $T = \emptyset$.

Apply the following operation repeatedly until $H$ is empty:

• In $H$, find and remove a triple $(i,j,w)$ that minimises $w$.

• See if $i$ and $j$ are in the same part of $P$. If not, discard this triple and try again.

• Now we have a pair $(i,j)$ and a part $X \in P$ such that $i\in X$, $j \in X$. We now know that $\{i,j\}$ has to be an edge in the subtree induced by $X$.

• Add $\{i,j\}$ to $T$.

• For all nodes $v \in X$, see if $v$ is closer to $i$ or $j$. Based on this information, refine the partition $P$ by replacing $X$ with $X_i$ and $X_j$, where $X_i \subseteq X$ contains the nodes that are closer to $i$, and $X_j$ similarly.

If I am not mistaken, the time complexity is roughly as follows, assuming appropriate data structures:

• We extract $O(N^2)$ triples.

• Only $O(N)$ triples will result in something added to $T$. These are the triples that require nontrivial work.

• For nontrivial triples, the operation that dominates is splitting. There we will need to check in the worst case $O(N)$ nodes.

• So overall the running time is something like $O(N^2) + O(N) O(N) = O(N^2)$.

• On top of this we pay whatever time we used to construct $H$. A simple solution is to just sort the triples $(i,j,w)$ by $w$. The cost depends on what kind of $w$ values you might have, but it isn't much worse than $O(N^2)$.

• Thanks for your idea, I managed to write the code in $O(N^2 \cdot \log (N^2))$ – someone12321 Sep 10 '17 at 14:34
• @someone12321: BTW, $O(\log N^2) = O(2\log N) = O(\log N)$. – j_random_hacker Sep 11 '17 at 4:42

Reconstructing an unrooted undirected weighted tree from its distance matrix is an important problem in bio-informatics, where it is used in the context of creating phylogenetic trees.

A commonly used tool is the algorithm of neigbour joining, a clustering method. It performs very simple computations in the matrix, basically repeatedly recalculating weighted distances. Its complexity is $\mathcal O(n^3)$.

A tree defines a metric which is "additive" and satisfies the so-called "four point condition". Neighbour joining is quite robust in the sense that is also constructs acceptable trees if the metric is not exactly additive. In the case of bio-informatics exact information is not always available.

Since you already have a matrix of shortest distances between all nodes in the graph, you can treat each of these pair values as an edge in a separate graph. Now, if you compute the minimum spanning tree of this graph, you get an undirected acyclic graph (forest), which will span across all $N$ nodes, preserving the shortest distances from the original matrix. You could use Kruskal's algorithm for this, which isn't that hard to implement, and it will run in $O(E$ log $N)$, where $E$ is the number of edges, and $N$ the number of vertices.