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

Question

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

Thanks in advance.

Answer 1

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

Answer 2

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.

Answer 3

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.