Given an undirected unweighted graph $G(V, E)$, there is an efficient algorithm to find the shortest paths between every pair of nodes. I am interested in the reverse problem, we want to reconstruct the original graph given the shortest distances between every pair of nodes.

**Reconstruction from shortest paths**

**INPUT**: An integer matrix $A$

**Question**: Is there a graph $G(V, E)$ such that $A_{(i,j)} $ is the shortest distance between nodes $i$ and $j$.

What is known about the complexity of this problem? Is it solvable by a polynomial-time algorithm? Is it NP-complete?