Reconstruct graph of N edges from a matrix of shortest pair distances (N*N) (i.e. result from Floyd-Warshall algorithm)

Question

I want to reconstruct a graph when given the results of a Floyd-Warshall shortest pair distances matrix, similar to the problem being solved in this question:

Is it possible to reconstruct graph if we have given matrix of shortest pairs

The only difference being that, whilst the problem from the linked-to question seeks to find a graph of $N-1$ edges, I want to produce a graph containing $N$ edges.

I've already found a more efficient way of solving the problem from the question linked above. Instead of using the solution offered there, I have found that building a minimal spanning tree also yields the correct result, namely a graph of $N-1$ edges that, when given as input to the Floyd-Warshall algorithm, produces exactly the matrix of minimum distance pairs with which we started.

Now we have one edge left to add. This is the part I am unable to figure out. It boils down to this:

I have a graph of $N-1$ edges, which is represented by a matrix of shortest pair distances. Out of a list of candidate edges, how can I efficiently (i.e. without brute forcing) find which edge to add that does not change even a single value in the matrix, preserving all minimum distances?

Thanks!

Answer 1

Pick any pair of vertices $u,v$ where it is possible to reach $v$ from $u$. Add an edge $u \to v$ with a length that is really large.

Answer 2

I've myself found a solution to the problem.

After you have computed the Minimum Spanning Tree, and thus have a graph of $n-1$ edges, you must iterate over the list of remaining edges. This list of edges must be sorted by weight, in nondecreasing order. For every edge, you check whether its weight is equal to the shortest distance between its constituent nodes. If it is, discard the edge and move on to the next in the list. The first edge you find, for which the previously mentioned test does not hold, is the edge that must be added to the graph.