Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
Now that I think I understand what you're going for, the answer is contained in your question. Just modify the Floyd-Warshall algo to keep track of redundant edges. We should close this question for scope. This isn't really a research-level question. –  John Moeller Dec 27 '11 at 21:34
I have posted a similar question on stackoverflow, which has been closed, because they think it did not suit. It will be great if this post can be kept open here, hope get more detailed and clearer comments... –  SoftTimur Dec 28 '11 at 2:26
Welcome to CSTheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. –  Kaveh Dec 30 '11 at 5:10
Do you want to change only one edge weight to ∞, or can you change multiple edges to ∞? In the latter case, I cannot see how to solve the problem efficiently (in terms of the number of output) right now. –  Tsuyoshi Ito Jan 4 '12 at 14:28
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.