patternMinor
Is it possible to reconstruct graph if we have given matrix of shortest pairs
Viewed 0 times
pairsgraphshortestpossiblereconstructmatrixgivenhave
Problem
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.
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.
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#81027, answer score: 6
Revisions (0)
No revisions yet.