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?
> 
> 
> 



Reconstructing a graph from shortest paths information
This problem is solvable in polynomial-time. Given a $V \times V$ distance matrix $A$, let $G$ be the graph with vertex set $V$, where $uw \in E(G)$ if and only if $A\_{uw}=1$. Note that $G$ is the only possible graph that has shortest distance matrix $A$. Now just compute all the shortest distances between all pairs of nodes in $G$ (this can be done in polynomial-time by [Dijkstra's Algorithm](https://en.wikipedia.org/wiki/Dijkstra's_algorithm)), and check that the distances agree with those in $A$. 


