I have a directed weighted graph $G = (V, E, W)$. $\forall i, j \in V, \exists e(i,j) \in E$ and $w(i,j)$ is an integer which could be $+\infty$, but never $-\infty$. 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_s = (V, E, W_s)$ (s for shortest).
In $G_s$, it is possible that for an edge from $i$ to $j$, $w_s(i,j) = w_s(i, k_0) + w_s(k_0, k_1) + ... w_s(k_n, j)$. Let us make from $G_s$ another graph $G''$ whose any element is same as $G_s$ except $w''(i,j) = +\infty \neq w_s(i,j)$. Therefore we know that an execution of a shortest paths algorithm on $G''$ will give $G_s$.
So given a $G_s$, I would like to find a set of graphs $\{G''_p : p \in P\}$, such that $\forall p\in P, i, j, w''_p(i,j) = w_s(i,j)$ or $+\infty$, and $G''_p$ can be reduced to $G_s$ 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?
