Given n by n points and the distance d between these points, I need to find the corresponding undirected weighted graph that would result in these distances. I tried using Prim's algorithm to find the MST, however this set is of size n-1 and does not include the n needed edges. E.g. given n by n distances
0 3 5
3 0 4
5 4 0
I need to find the corresponding edges:
1 - 2 = 3
1 - 3 = 5
2 - 3 = 4
Which results in the graph:
3
1 --------- 2
\ /
\5 /4
\ /
\ /
3
However Prim's would return only the first 2 edges since a MST doesn't contain any cycles.
One graph that would result in these distances is the graph that has an edge from every node to every other node and the length of that edge is the distance according to the matrix. (I'm not sure what you mean by unweighted directed because the example you give appears to be undirected and I'm not sure what the difference is between weights and lengths here).
Another option would be to consider the distances in increasing order, as you have done with Prim's algorithm, and, as well as checking to see if the edge is required to connect its two ends, check to see if the minimum distance between those ends in the graph reconstructed so far is the same as the distance in the matrix. If it is not, add the edge even if the ends are connected in the graph so far.