I have a directed weighted graph $G = (V, E, W)$. There is always an edge from a vertex $i$ to another one $j$, the weight $w(i,j)$ could be positive infinity, and there does not exist any negative cycle.

An execution of some algorithms will find the lengths (summed weights) of the shortest paths between all pairs of vertices though it does not return details of the paths themselves. For instance, Floyd–Warshall algorithm is straightforward, and it works. Let us denote the result by $G' = (V, E, W')$.

In $G'$, it is possible that for an edge from $i$ to $j$, $w'(i,j) = w'(i, k_0) + w'(k_0, k_1) + \dots + w'(k_n, j)$. Let us make from $G'$ another graph $G''$ whose any element is same as $G'$ except $w''(i,j) = \infty \neq w'(i,j)$. Therefore we know that an execution of a shortest paths algorithm on $G''$ will give $G'$.

So given a $G'$, I would like to find all the graphs like $G''$, such that for all $i$ and $j$, $w''(i,j) \in \{ w'(i,j), \infty\}$, and $G''$ can be reduced to $G'$ via a shortest paths algorithm.

Hope my question is clear... I do not know if an algorithm for this exists already, does anyone have any idea?

  • 1
    $\begingroup$ I don't understand what you are getting at here. What is $G'$, the graph consisting of the shortest paths? Or a graph with edges from $i$ to $j$ with the weight of the shortest path from $i$ to $j$ in $G$? $\endgroup$
    – Raphael
    Jun 27, 2012 at 13:04
  • $\begingroup$ @Raphael, G' is your second case (shortest path graph), but I don't know what is G"? $\endgroup$
    – user742
    Jun 27, 2012 at 19:25
  • 1
    $\begingroup$ Ah, I believe I start to see the question: Given a tree $T$, enumerate all graphs whose shortest-path tree is $T$. Is this correct? I am still a little confused by the restrictions on the $G''$ you define. If my interpretation is correct, note this: there are infinitely many such graphs. $\endgroup$
    – Raphael
    Jun 28, 2012 at 12:33
  • $\begingroup$ Do you mean: every $G''$ is obtained by removing one or more edges from $G$, subject to the criterion that the distances between all vertices remain the same? Or may edges be added as well? $\endgroup$ Nov 24, 2014 at 17:05

1 Answer 1


Nearest neighbor, nearest insertion, farthest insertion, and cheapest insertion are just some heuristics to get you started. You can also model the problem as a maximum flow integer program.


  • $\begingroup$ Would you describe it more? $\endgroup$
    – user742
    May 26, 2012 at 7:56
  • $\begingroup$ your answer is very vague, can you elaborate more on it? $\endgroup$ Jul 27, 2012 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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