Return to Revisions

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), and check that the distances agree with those in $A$.