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