This problem is solvable in polynomial-time.  Given a $V \times V$  distance matrix $A$, let $G(A)$ 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$.