Given all pairs shortest paths matrix, find graph with minimum total sum of edges
I think your approach works even if you did not give much details.

Let's call $A$ the matrix. First you sort all pairs ($i$, $j$) with $i &lt; j$ and $A_{ij}$ increasing. You also have initially a graph $G$ with all nodes and no edges.

Then you process the pairs ($i$, $j$) one by one deciding whether to add an edge between nodes $i$ and $j$:


compute $D$, the total weight of the shortest path existing in $G$ from $i$ to $j$ ($+\infty$ if no path).


if $D &lt; A_{ij}$, the problem has no solution,
if $D = A_{ij}$, do nothing,
if $D &gt; A_{ij}$, add the edge between $i$ and $j$ of weight $A_{ij}$ to $G$.



If the shortest path from $i$ to $j$ is undirect, it necessarly has already been placed as you sorted your pairs increasing.