5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – rus9384 Sep 8 '17 at 17:36
  • 1
    $\begingroup$ Can the weights on the original tree be negative? zero? $\endgroup$ – D.W. Sep 8 '17 at 20:43
  • $\begingroup$ 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$. $\endgroup$ – someone12321 Sep 9 '17 at 7:42
6
$\begingroup$

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

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

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.

$\endgroup$
1
$\begingroup$

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.

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