2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "If it is, discard the edge and move on to the next in the list." Well, you can just add it as well. In fact, if the matrix of shortest pair distances (N*N) is computed from a weight function on edges (e.g. result from Floyd-Warshall algorithm), you can just add any edge not in the Minimum Spanning tree whose weight is the entry of the matrix that corresponds to the two endpoints of that edge or larger than that entry. Check this answer for more related information. $\endgroup$ – Apass.Jack Mar 17 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.