# Find all the special graphs which can reduced to the shortest paths graph

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?

• 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$? Commented Jun 27, 2012 at 13:04
• @Raphael, G' is your second case (shortest path graph), but I don't know what is G"?
– user742
Commented Jun 27, 2012 at 19:25
• 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. Commented Jun 28, 2012 at 12:33
• 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? Commented Nov 24, 2014 at 17:05